題目

利用前序(Preorder)和中序(Inorder)去建構一棵樹

解題方法

在解決此問題，需要先知道Preorder和Inorder是如何相互應用，結合出一棵唯一樹。
首先，Preorder的產生為DLR，而Inorder為LDR。L為左子節點，D為父節點，R為右子節點，而在Preorder的第一元素都為一棵樹的Root。
只要熟悉此相關Tree之特性，其問題就較容易解決。分別找出Root及其對應左、右子樹。

程式碼

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return findNode(0,preorder.size()-1,0,inorder.size()-1,preorder,inorder);
    }

    TreeNode* findNode(int preStart,int preEnd,int inStart,int inEnd,vector<int>& preorder, vector<int>& inorder)
    {
        if(preStart > preEnd || inStart > inEnd)
            return nullptr;
        
        int idx = 0;
        
        TreeNode* node = new TreeNode(preorder[preStart]);
        
        for(int i = inStart;i<=inEnd;++i) 
        {
            if(node->val == inorder[i])
                idx = i;
        }
        
        node->left = findNode(preStart+1,preEnd+idx-1,inStart,idx-1,preorder,inorder);
        node->right = findNode(preStart+idx+1-inStart,preEnd,idx+1,inEnd,preorder,inorder);
        
        return node;        
    }
};