105. Construct Binary Tree from Preorder and Inorder Traversal
給定兩個整數數組 preorder 和 inorder，其中 preorder 是一棵二元樹的前序遍歷，inorder 是同一棵二元樹的中序遍歷，構造並返回這棵二元樹。
範例：
輸入：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 輸出：[3,9,20,null,null,15,7]
這表明根據給定的前序和中序遍歷結果，可以構造出一棵二元樹，其結構如輸出所示。
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
# The first element in preorder is the root
root_val = preorder[0]
root = TreeNode(root_val)
# Find the index of the root in inorder list
mid = inorder.index(root_val)
# Recursively construct the left and right subtrees
root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
return root
88.15MB, 143ms
C++
class Solution {
private:
unordered_map<int, int> inorderMap;
int preorderIndex;
TreeNode* buildTreeHelper(vector<int>& preorder, int left, int right) {
if (left > right) return nullptr;
int rootValue = preorder[preorderIndex++];
TreeNode* root = new TreeNode(rootValue);
root->left = buildTreeHelper(preorder, left, inorderMap[rootValue] - 1);
root->right = buildTreeHelper(preorder, inorderMap[rootValue] + 1, right);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
preorderIndex = 0;
// Build a hash map to store value -> its index relations
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
return buildTreeHelper(preorder, 0, inorder.size() - 1);
}
};
26.16MB, 12ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
if (!preorder.length || !inorder.length) {
return null;
}
// The first element in preorder is the root
const rootVal = preorder[0];
const root = new TreeNode(rootVal);
// Find the index of the root in inorder array
const mid = inorder.indexOf(rootVal);
// Recursively construct the left and right subtrees
root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
return root;
};
125.4MB, 154ms
