7. 重建二叉树

 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

class Solution
{
private:
    TreeNode* buildTree(vector<int> &i_preorder, int preLeft, int preRight,
        vector<int> &i_inorder, int inLeft, int inRight)
    {
        if(preLeft > preRight || inLeft > inRight) return nullptr;

        auto root = new TreeNode(i_preorder[preLeft]);
        if(preLeft == preRight)
        {
            return root;
        }
        else
        {
            int rootIndexAtInorder = find(i_inorder.begin(), i_inorder.end(), i_preorder[preLeft]) - i_inorder.begin();
            int leftSubTreeNodeCount = rootIndexAtInorder - inLeft;
            int rightSubTreeNodeCount = inRight - rootIndexAtInorder;

            root->left = buildTree(i_preorder, preLeft + 1, preLeft + leftSubTreeNodeCount,
                i_inorder, inLeft, rootIndexAtInorder - 1);
            root->right = buildTree(i_preorder, preRight - rightSubTreeNodeCount + 1, preRight,
                i_inorder, rootIndexAtInorder + 1, inRight);

            return root;
        }
    }
public:
    // TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    TreeNode* buildTree(vector<int> &i_preorder, vector<int> &i_inorder)
    {
        if(i_preorder.empty() || i_preorder.size() != i_inorder.size()) return nullptr;

        return buildTree(i_preorder, 0, i_preorder.size() - 1, i_inorder, 0, i_inorder.size() - 1);
    }
};