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

 

递归遍历

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

二叉搜索树

树的平衡性

路径搜索

最近共同祖先问题

 

挖个坑,有空填

 

发表评论

邮箱地址不会被公开。 必填项已用*标注