当前位置：首页 > news >正文

力扣（105. 从前序与中序遍历序列构造二叉树，106. 从中序与后序遍历序列构造二叉树）

news 2025/8/1 16:29:19

题目1链接
题目1：
在这里插入图片描述

思路：使用前序确定根，使用中序分左右子树，分治法。

难点：如何控制递归确定左右子树。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*///遍历前序确定根，使用中序来分树class Solution {
public:TreeNode* findRoot(vector<int>& preorder, vector<int>& inorder, int& preindex, int left, int right){if(left>right){return nullptr;}//首先前序确定根TreeNode* root = new TreeNode(preorder[preindex]);//遍历中序，找根，分左右int rootindex = left;while(rootindex<=right){if(inorder[rootindex] == preorder[preindex])break;  //找到了！rootindex++;}preindex++;//   [left, rootindex-1] rootindex [rootindex+1, right]root->left = findRoot(preorder, inorder, preindex, left, rootindex-1);root->right = findRoot(preorder, inorder, preindex, rootindex+1, right);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;return findRoot(preorder, inorder, i,0, inorder.size()-1);}
};

题目2链接

题目2：
在这里插入图片描述
题目1会了，题目二就一定会了！

注意：后序（左右根）从后往前确定根，中序分左右子树。
递归时，先遍历右子树，再遍历左子树。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* findRoot(vector<int>& inorder, vector<int>& postorder, int& postindex, int left, int right){if(left>right){return nullptr;}//首先后序确定根TreeNode* root = new TreeNode(postorder[postindex]);//遍历中序，找根，分左右int rootindex = left;while(rootindex<=right){if(inorder[rootindex] == postorder[postindex])break;  //找到了！rootindex++;}postindex--;//   [left, rootindex-1] rootindex [rootindex+1, right]root->right = findRoot(inorder, postorder, postindex, rootindex+1, right);root->left = findRoot(inorder, postorder, postindex, left, rootindex-1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i = postorder.size() - 1;return findRoot(inorder, postorder, i, 0, inorder.size()-1);}
};