每天一道LeetCode-----根據先序周遊和中序周遊還原二叉樹

Construct Binary Tree from Preorder and Inorder Traversal

原題連結Construct Binary Tree from Preorder and Inorder Traversal

給定一個二叉樹的先序周遊和中序周遊，要求重制這棵二叉樹

另先序周遊的序列為preorder，中序周遊的序列為inorder，節點個數為n

根據先序周遊的特點，可知preorder[0]一定是整棵二叉樹的根節點，那麼，如果已确定根節點值在中序周遊序列inorder中的下标是i，就一定有

• inorder[0 : i - 1]這些值屬于根節點的左子樹
• inorder[i + 1, n - 1]這些值屬于根節點的右子樹

因為中序周遊是從最左邊開始周遊，是以當周遊到根節點inorder[i]時，之前周遊到的節點一定都屬于左子樹

那麼現在的目的就是如何确定左右子樹的根節點，由先序周遊可知

• preorder[0 + 1]一定是左子樹的根節點
• preorder[0 + 1 + (i - 0)]一定是右子樹的根節點

因為先序周遊周遊到的節點順序是從根節點到最左邊，再到右邊，那麼既然已經直到左子樹上有多少節點了(i - 0個)，那麼就可以确定右子樹的根節點

直接遞歸即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(, , inorder.size() - , preorder, inorder);  
    }
private:
    /* preStart : 目前根節點在preorder中的下标
     * [inStart:inEnd]  : 以preorder[preStart]為根節點的子樹的節點值在inorder的範圍
     */
    TreeNode* buildTree(int preStart, int inStart, int inEnd, vector<int>& preorder, vector<int>& inorder)
    {
        if(preStart >= preorder.size() || inStart > inEnd)
            return nullptr;

        /* 申請根節點　*/
        TreeNode* root = new TreeNode(preorder[preStart]);
        /* 尋找根節點在inorder的位置，拆分左右子樹 */
        int inIndex = ;
        for(int i = inStart; i <= inEnd; ++i)
        {
            if(inorder[i] == preorder[preStart])
            {
                inIndex = i;
                break;
            }
        }

        root->left = buildTree(preStart + , inStart, inIndex - , preorder, inorder);
        root->right = buildTree(preStart +  + inIndex - inStart, inIndex + , inEnd, preorder, inorder);
        return root;
    }
};
           

本題主要需要弄清楚如何進行遞歸，當然拆分成左右子樹是個很好的方法，不夠不太容易想到。

先序周遊可以直到根節點，而中序周遊可以确定該根節點的左右子樹的取值範圍，進而不斷拆分下去，最終求解