【数据结构】二叉树经典题目

桃扇骨 2024-03-16 18:16 107阅读 0赞

### 1. [二叉树创建字符串][Link 1] ###

相信大部分人看了题目描述之后，都会和我一样一脸的懵逼。直到我看到了一个描述才恍然大悟  
![309e386e0404b8505ce6e76eb5251e89.png][]  
分为3种情况：

1.  左右都为空 --省略
2.  右为空，左不为空 – 省略
3.  左为空，右不为空–不省略

这里复习一下二叉树的前序遍历、中序遍历、和后序遍历  
![63e18849c09e4b43591060b30d5d69f3.png][]  
前序的结果是：ABDEGCF  
中序的结果是：DBGEACF  
后序的结果是：DGEBFCA

class Solution {
    public:
    	string tree2str(TreeNode* root) {
    		if (root == nullptr)
    		{
    			return "";
    		}
    		string str = to_string(root->val);
    		if (root->left || root->right) // 特别注意这个条件
    		{
    			str += "(";
    			str += tree2str(root->left);
    			str += ")";
    		}
    		if (root->right)
    		{
    			str += "(";
    			str += tree2str(root->right);
    			str += ")";
    		}
    		return str;
    	}
    };

### 2. [二叉树的层序遍历][Link 2] ###

![3fad38093861707e1ca55baa65831a83.png][]

思路大致是这样的：  
一个队列，接着一个`levelSize`来记录每层有几个数据，如果这个数字是0，则表示这层的数据出完

![65e7aeafc42c0e5fc7646c5c67e080c6.png][]  
出3将9和20带到队列，levelSize为2 。如此循环下去。  
如果这个队列不为空，就一直循环下去，直到这个队列为空为止。  
代码实现：

class Solution {
    public:
    	vector<vector<int>> levelOrder(TreeNode* root) {
    		queue<TreeNode*> q;
    		int levelSize = 0;
    		if (root)
    		{
    			q.push(root);
    			levelSize = 1;
    		}
    		vector<vector<int>> vv;
    		while (!q.empty()) // 如果队列不为空，就继续
    		{
    			// 通过levelSize控制一层一层的出
    			vector<int> v;
    			while (levelSize--)
    			{
    				TreeNode* front = q.front();
    				q.pop();
    				v.push_back(front->val);
    				if (front->left)
    				{
    					q.push(front->left);
    				}
    				if (front->right)
    				{
    					q.push(front->right);
    				}
    			}
    			vv.push_back(v);
    			// 更新下一层的个数
    			levelSize = q.size();
    		}
    		return vv;
    	}
    };

### 3. [二叉树的层序遍历Ⅱ][Link 3] ###

![7cb87d04fb5707ee4b2a3ea9cbbf8081.png][]  
这个题目与上一题目，差不多，我们只需要将最后的**答案逆置**即可

### 4. [二叉树的最近公共祖先][Link 4] ###

![8fb101c6cc04b68f848b3a665da8089c.png][]  
![52ba944e9abc74a0ec10b2457305f3e3.png][]  
思路一：公共祖先的特征，如果一个在左子树，一个在右子树。那么这个节点就是公共祖先。

class Solution {
    public:
    	bool isInTree(TreeNode* root, TreeNode* x) {
    		if (root == nullptr) {
    			return false;
    		}
    		return x == root
    			|| isInTree(root->left, x)
    			|| isInTree(root->right, x);
    	}
    	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    		if (root == nullptr) {
    			return nullptr;
    		}
    		if (p == root || q == root) {
    			return root;
    		}
    		// 判断p节点是在root的左边还是右边
    		bool pInLeft = isInTree(root->left, p);
    		bool pInRight = !pInLeft;
    		// 判断q节点是在root的左边还是右边
    		bool qInLeft = isInTree(root->left, q);
    		bool qInRight = !qInLeft;
    
    		if ((pInLeft && qInRight) || (pInRight && qInLeft)) {
    			return root;
    		}
    		// 如果都在左边，则转换为在左树寻找公共祖先
    		else if (pInLeft && qInLeft) {
    			return lowestCommonAncestor(root->left, p, q);
    		}
    		else {
    			return lowestCommonAncestor(root->right, p, q);
    		}
    	}
    };

思路二：**公共祖先的特征，如果一个在我的左子树，一个在我的右子树，我就是公共祖先**  
如果是搜索二叉树可以优化到O(N)

1.  一个比根小，一个比根大，根就是公共祖先
2.  都比根小，递归左树查找
3.  都比根大，递归右树查找  
    但是这个题目我们并不是搜索二叉树，要求优化到O(N)  
    这里只能使用另外一种思路，将p和q的路径求出来，放到容器当中，转换为路径相交问题

class Solution {
    public:
    	bool getPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) {
    		if (root == nullptr) {
    			return false;
    		}
    		path.push(root);
    		if (root == x) {
    			return true;
    		}
    		if (getPath(root->left, x, path)) {
    			return true;
    		}
    		if (getPath(root->right, x, path)) {
    			return true;
    		}
    		path.pop();
    		return false;
    	}
    	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    		stack<TreeNode*> pPath, qPath;
    		getPath(root, p, pPath);
    		getPath(root, q, qPath);
    		while (pPath.size() != qPath.size()) {
    			if (pPath.size() > qPath.size()) {
    				pPath.pop();
    			}
    			else {
    				qPath.pop();
    			}
    		}
    		while (pPath.top() != qPath.top()) {
    			pPath.pop();
    			qPath.pop();
    		}
    		return pPath.top();
    	}
    };

上述代码的关键在于找到每个节点的路径

### 5. [二叉搜索树与双向链表][Link 5] ###

![1af99c26c19b73b5c037d7818c3434e1.png][]  
看到这个题目我们的第一个想法可能是把所有的节点拿出来，然后尾插到一个双向链表上，其实并没有这么简单，我们能够想到的出题人当然也能够想到。  
这个题目有以下几个要求：  
![ac0f41236ed15c1e991113606f11bef8.png][]  
我们需要在原树上进行操作。

class Solution {
    public:
    	void inorderTraversal(TreeNode* cur, TreeNode*& prev) {
    		if (cur == nullptr) {
    			return;
    		}
    		inorderTraversal(cur->left, prev);
    		cur->left = prev;
    		if (prev) {
    			prev->right = cur;
    		}
    		prev = cur;
    		inorderTraversal(cur->right, prev);
    	}
    	TreeNode* Convert(TreeNode* pRootOfTree) {
    		TreeNode* prev = nullptr;
    		inorderTraversal(pRootOfTree, prev);
    		TreeNode* head = pRootOfTree;
    		while (head && head->left) {
    			head = head->left;
    		}
    		return head;
    	}
    };

![efefe1f816dc9c264941c0e4e4779cec.png][]  
以上的这幅图是精髓所在

### 6. [从前序与中序遍历序列构造二叉树][Link 6] ###

![1e0d2e26b4289c3680b1f965bd1c6558.png][]  
![7d6a097a00207b186561eb97f40c8602.png][]

class Solution {
    public:
    	TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& previ, int inbegin, int inend) {
    		if (inbegin > inend) {
    			return nullptr;
    		}
    		TreeNode* root = new TreeNode(preorder[previ]);
    		// 分割出左右区间
    		int rooti = inbegin;
    		while (rooti <= inend) {
    			if (inorder[rooti] == preorder[previ]) {
    				break;
    			}
    			else {
    				rooti++;
    			}
    		}
    		++previ;
    		// [inbegin, rooti - 1], rooti, [rooti + 1, inend]
    		root->left = _buildTree(preorder, inorder, previ, inbegin, rooti - 1);
    		root->right = _buildTree(preorder, inorder, previ, rooti + 1, inend);
    		return root;
    	}
    	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    		int i = 0;
    		return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    	}
    };

### 7. [二叉树的前序遍历(非递归)][Link 7] ###

![3395cc82c8806a6306985f760f8de8b5.png][]

class Solution {
    public:
    	vector<int> preorderTraversal(TreeNode* root) {
    		stack<TreeNode*> st;
    		TreeNode* cur = root;
    		vector<int> v;
    		while (cur || !st.empty()) {
    			// 1. 开始访问一棵树
    			// 2. 左路节点
    			// 3. 左路节点的右子树
    			while (cur) {
    				v.push_back(cur->val);
    				st.push(cur);
    				cur = cur->left;
    			}
    			// 访问右子树
    			TreeNode* top = st.top();
    			st.pop();
    			// 子问题访问右子树
    			cur = top->right;// 这个地方非常重要
    		}
    		return v;
    	}
    };

### 8. [二叉树的中序遍历(非递归)][Link 8] ###

class Solution {
    public:
    	vector<int> inorderTraversal(TreeNode* root) {
    		stack<TreeNode*> st;
    		TreeNode* cur = root;
    		vector<int> v;
    		while (cur || !st.empty()) {
    			while (cur) {
    				st.push(cur);
    				cur = cur->left;
    			}
    			// 栈里面取到左路节点，左路节点的左子树访问完了
    			TreeNode* top = st.top();
    			st.pop();
    			v.push_back(top->val);
    
    			cur = top->right;
    		}
    		return v;
    	}
    };

### 8. [二叉树的后序遍历(非递归)][Link 9] ###

class Solution {
    public:
    	vector<int> postorderTraversal(TreeNode* root) {
    		stack<TreeNode*> st;
    		TreeNode* cur = root;
    		vector<int> v;
    		TreeNode* prve = nullptr;
    		while (cur || !st.empty()) {
    			while (cur) {
    				st.push(cur);
    				cur = cur->left;
    			}
    			// 栈里面取到左路节点，左路节点的左子树访问完了
    			TreeNode* top = st.top();
    			// 右为空或者右已经访问过了，可以访问根节点
    			if (top->right == nullptr || top->right == prve) {
    				v.push_back(top->val);
    				st.pop();
    				prve = top;
    			}
    			else {
    				cur = top->right;
    			}
    		}
    		return v;
    	}
    };

这里对非递归的三种代码进行对比：

![ebe154ef449a6c643e29afa034e89b2d.png][]

[Link 1]: https://leetcode.cn/problems/construct-string-from-binary-tree/
[309e386e0404b8505ce6e76eb5251e89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/1158b97a426348d8a9b3c1d3258b2216.png
[63e18849c09e4b43591060b30d5d69f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/682d1aa0ae9e437192674cb8b092ff18.png
[Link 2]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[3fad38093861707e1ca55baa65831a83.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/dc4e0f9c59b947d997cb06cdc62449a7.png
[65e7aeafc42c0e5fc7646c5c67e080c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/af3e28adde8e4567b47cd44d160cd63c.png
[Link 3]: https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
[7cb87d04fb5707ee4b2a3ea9cbbf8081.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2cb9ba821fe541489aa24f8104e44121.png
[Link 4]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[8fb101c6cc04b68f848b3a665da8089c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c5cf6a02755a4360b38b43e72d8baf79.png
[52ba944e9abc74a0ec10b2457305f3e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2e2190dc51164a2c9bab6d68318cc3cc.png
[Link 5]: https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[1af99c26c19b73b5c037d7818c3434e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/de8d8b723f074c5a95489a9dfbc89f32.png
[ac0f41236ed15c1e991113606f11bef8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/267669e7919d4f29a709fa1d05e134f7.png
[efefe1f816dc9c264941c0e4e4779cec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e0914ff4711145409d5cc45e428e15d0.png
[Link 6]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[1e0d2e26b4289c3680b1f965bd1c6558.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8137f7a3afce4d51b8bda50156871c85.png
[7d6a097a00207b186561eb97f40c8602.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/617eeb769ed44b58bba851a1b14da0fe.png
[Link 7]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[3395cc82c8806a6306985f760f8de8b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9eb37e31b0f44e17b1c3ccde9b865fb6.png
[Link 8]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[Link 9]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[ebe154ef449a6c643e29afa034e89b2d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/613d77a841ba416b8786c449d3e59d60.png