题目地址：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
题目描述：输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
比如：该二叉树
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
递归方法
可以知道的是：
前序遍历一棵二叉树的结果肯定是：
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
中序遍历一棵二叉树的结果是：
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
那么我们可以采取以下思路：
（设定先序遍历为preorder，中序遍历为inorder）
- 设定preorder[0] 为根节点 root
- 在 inorder 中寻找根节点所在的位置，然后计算 左子树 的结点个数
- 然后就可以递归建树了
代码如下：
class Solution {
public:
unordered_map<int, int> index;
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
int n = preorder.size();
for (int i = 0; i < n; i++) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
TreeNode *myBuildTree(vector<int> &preorder, vector<int> &inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
int root_pre_idx = preorder_left;
TreeNode *root = new TreeNode(preorder[root_pre_idx]);
int root_in_idx = index[preorder[root_pre_idx]];
int left_tree_cnt = root_in_idx - inorder_left;
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + left_tree_cnt, inorder_left, root_in_idx - 1);
root->right = myBuildTree(preorder, inorder, preorder_left + left_tree_cnt + 1, preorder_right, root_in_idx + 1, inorder_right);
return root;
}
};
Top comments (0)