算法导论总结（三）树

树作为重要的数据结构，在很多领域有着重要的用途。在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;
	}

 

递归遍历

使用递归方式遍历树，这个大家都会，就不说了。

二叉搜索树

树的平衡性

路径搜索

最近共同祖先问题

 

挖个坑，有空填