105 从前序与中序遍历序列构造二叉树

本文最后更新于：2021年2月15日 下午

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

Solution

其他相似题型 [106 从中序与后序遍历序列构造二叉树] 、[654 最大二叉树]

参考 代码随想录

  • 递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// @lc code=start
/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0 || inorder.size() == 0) return nullptr;
        return traversal(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
private:
    TreeNode* traversal(vector<int>& preorder, int preorderBegin, int preorderEnd, 
                        vector<int>& inorder, int inorderBegin, int inorderEnd) {
        if (preorderBegin == preorderEnd) return nullptr;

        int rootVal = preorder[preorderBegin];
        TreeNode* root = new TreeNode(rootVal);
        if (preorderEnd-preorderBegin == 1) return root;

        int delimIndex;
        for(delimIndex = inorderBegin; delimIndex < inorderEnd; ++delimIndex) {
            if (inorder[delimIndex] == rootVal) break;
        }

        // 切割中序数组, 左闭右开
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimIndex;
        int rightInorderBegin = delimIndex + 1;
        int rightInorderEnd = inorderEnd;
        // 切割前序数组, 左闭右开
        int leftPreorderBegin = preorderBegin + 1;
        int leftPreorderEnd = leftPreorderBegin + (leftInorderEnd - leftInorderBegin);
        int rightPreorderBegin = leftPreorderEnd;
        int rightPreorderEnd = preorderEnd;

        root->left = traversal(preorder, leftPreorderBegin, leftPreorderEnd,
                                inorder, leftInorderBegin, leftInorderEnd);
        root->right = traversal(preorder, rightPreorderBegin, rightPreorderEnd,
                                inorder, rightInorderBegin, rightInorderEnd);
        return root;
    }
};
// @lc code=end