树作为重要的数据结构,在很多领域有着重要的用途。在LeetCode中对数的考察主要分为三个方面,一是树的遍历,二是BST(二叉搜索树),三是和树相关的算法。有时,树也常常被看做一个图,做BFS和DFS,树的考察是相当灵活的。这篇博客就这些问题做部分小结。
树的种类
参考维基百科定义,需要掌握如下概念。
完全二叉树
平衡二叉树
理想二叉树(完美二叉树)
树的遍历
树的遍历方法主要分为三种:先序 PreOrder,中序 InOrder, 后序 PostOrder,还有一种方式也会用到,叫做 层序 LevalOrder。
从实现上讲,上面几种方式都可以通过递归的方式和迭达方式实现,如果不是尾递归的话,空间复杂度就是O(lg(n)),所以使用迭代方式遍历树就有空间复杂度O(1)的优势,并且迭代减少了函数调用的开销(实际时间未必比递归方式少),所以下面主要讲这几种遍历方式的迭代实现。
迭代遍历
先序遍历
void preorder(TreeNode* root){ if (!root){ return; } stack<TreeNode*> stk; stk.push(root); while (!stk.empty()){ auto t = stk.top(); stk.pop(); if (t->right){ stk.push(t->right); } if (t->left){ stk.push(t->left); } cout << t->val; } return; }
中序遍历
void inorderTraversal(TreeNode *root) { if (!root){ return; } stack<TreeNode*> stk; TreeNode* p = root; while (p || !stk.empty()){ while (p){ stk.push(p); p = p->left; } p = stk.top(); stk.pop(); cout << p->val; p = p->right; } }
后序遍历
vector<int> postorderTraversal(TreeNode* root) { // reco if (!root){ return{}; } vector<int> path; TreeNode* prev = NULL; stack<TreeNode*> stk; stk.push(root); while (!stk.empty()){ auto t = stk.top(); if ((!t->left && !t->right) || // t是叶节点,或者 (prev && (t->left == prev || t->right == prev))){ // t有孩子刚刚遍历过 path.push_back(t->val); stk.pop(); prev = t; } else{ if (t->right){ stk.push(t->right); } if (t->left){ stk.push(t->left); } } } return path; }
层序遍历
层序遍历就是广度优先搜索,只是注意,风格上与上面有两点不同,一是使用队列而不是栈,二是使用NULL指针标记每层的末尾节点,用来区分层次。
void levelorder(TreeNode* root){ if (!root){ return; } queue<TreeNode*> q; q.push(root); q.push(NULL); while (!q.empty()){ auto t = q.front(); q.pop(); if (t){ if (t->right){ q.push(t->right); } if (t->left){ q.push(t->left); } cout << t->val; } else{ if (!q.empty){ q.push(NULL); cout << endl; } } } return; }
递归遍历
使用递归方式遍历树,这个大家都会,就不说了。
二叉搜索树
树的平衡性
路径搜索
最近共同祖先问题
挖个坑,有空填