Leetcode105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary

Construct Binary Tree from Preorder and Inorder Traversal:

用preorder和inorder來重建binary tree

preorder(前序) : 中 -> 左 -> 右

inorder(中序) : 左 -> 中 -> 右

Python

遞歸法

class Solution:
    def buildTree(self, preorder: 'List[int]', inorder: 'List[int]') -> TreeNode:
        if not preorder : return None
        root=TreeNode(preorder[0])   #根節點
        index=inorder.index(preorder[0])  
        root.left=self.buildTree(preorder[1:index+1],inoreder[:index])  #左節點
        root.right = self.buildTree(preorder[index + 1 :],inorder[index+1 :])  #右節點
        return root

C++

遞歸法

對於每一次遞歸，我們都可以確定該二叉樹的根節點以及其左子樹和右子樹的preorder和inorder。在遞歸中，我們首先需要找到當前二叉樹的根節點，可以在preorder中找到。由於preorder的順序是根節點、左子樹、右子樹，因此在preorder中找到的根節點必然是當前子樹的根節點。找到了根節點之後，我們需要在inorder中確定其左子樹和右子樹。inorder的順序是左子樹、根節點、右子樹，因此我們可以根據preorder中根節點的位置，將inorder劃分為左子樹和右子樹兩個部分。接下來，我們可以遞歸構造左子樹和右子樹，並將它們作為根節點的左子樹和右子樹。在遞歸結束之後，我們就構造出了整棵二叉樹。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pre_left, int pre_right, int in_left, int in_right) {
        if (pre_left > pre_right) {
            return nullptr;
        }
        int pre_root = pre_left;
        int in_root = find(inorder.begin() + in_left, inorder.begin() + in_right, preorder[pre_root]) - inorder.begin();
        int left_size = in_root - in_left;

        TreeNode* root = new TreeNode(preorder[pre_root]);
        root->left = build(preorder, inorder, pre_left + 1, pre_left + left_size, in_left, in_root - 1);
        root->right = build(preorder, inorder, pre_left + left_size + 1, pre_right, in_root + 1, in_right);

        return root;
    }
};