leetcode 105 從前序與中序遍歷序列構造二叉樹

• 2021 年 4 月 14 日
• 筆記
• C++, leetcode

前序遍歷 + 中序遍歷 = 可復原樹
後序遍歷 + 中序遍歷 = 可復原樹
前序遍歷 + 後序遍歷 = 不可

分析：

前序遍歷第一個值即為根節點，但是無法知道左子樹有幾個節點，也就確定不了左右子樹

中序遍歷如果能知道根節點，就能知道左子樹、右子樹各自節點數。

組合兩者，由前序得到根節點，再由中序判別左、右子樹個數。

設前序數組的左邊界為pre_left,右邊界為pre_right
中序數組的左邊界為ino_left,右邊界為ino_right

那麼根節點pre_root就為 preoder[pre_left]
在inorder數組中找到preoder[pre_left]這個值，假設它的index為 ino_root
那麼左子樹個數size_left_subtree為 ino_root-ino_left

其中在inorder數組中找到preoder[pre_left]，可以進行優化，預先遍歷一次preoder，將裏面的值存到unorder_map中當作Key，將它的index設為val。後續查找的時候直接取即可。

這樣一來:
左子樹:
在preorder中的下標範圍為[pre_root+1,pre_root+size_left_subtree]
在inorder中的下標範圍為[ino_left,ino_root-1]
右子樹:
在preoder中的下標範圍為[pre_root+size_left_subtree+1,pre_right]
在inorder中的下標範圍為[ino_root+1,ino_right]

很明顯，每做一次可以將當前節點創建，然後拆分成左子樹、右子樹，對於兩者分別看成根節點，帶入各自範圍再進行遞歸，就可以構造整顆樹

/**
 * 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 {
    unordered_map<int,int> index;
    TreeNode* buildHelper(vector<int>& preorder, vector<int>& inorder,int pre_left,int pre_right,int ino_left,int ino_right)
    {
        if(pre_left>pre_right||ino_left>ino_right) return nullptr;

        int pre_root = pre_left;

        int ino_root = index[preorder[pre_root]];

        TreeNode* node = new TreeNode(preorder[pre_root]);

        int size_left_subtree = ino_root-ino_left;
        node->left = buildHelper(preorder,inorder,pre_left+1,pre_left+size_left_subtree,ino_left,ino_root-1);
        node->right = buildHelper(preorder,inorder,pre_left+size_left_subtree+1,pre_right,ino_root+1,ino_right);
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for(int i = 0; i < n; ++i)
        {
            index[inorder[i]] = i;
        }
        return buildHelper(preorder,inorder,0,n-1,0,n-1);
    }
};