106. Construct Binary Tree from Inorder and Postorder Traversal
給定兩個整數數組 inorder 和 postorder，其中 inorder 是一棵二元樹的中序遍歷，postorder 是同一棵二元樹的後序遍歷，構造並返回這棵二元樹。
範例：
輸入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 輸出：[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, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not inorder or not postorder:
return None
# The last element in postorder is the root
root_val = postorder.pop()
root = TreeNode(root_val)
# Find the index of the root in inorder list
inorder_index = inorder.index(root_val)
# Recursively construct the right and left subtrees
# Note: it's crucial to construct the right subtree first because we are popping from the end of postorder
root.right = self.buildTree(inorder[inorder_index + 1:], postorder)
root.left = self.buildTree(inorder[:inorder_index], postorder)
return root
53.02MB, 109ms
C++
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// Create a map to store the index of each value in the inorder array for quick lookup
unordered_map<int, int> inorderMap;
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
// Start the recursive construction of the tree
return buildTreeRecursive(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorderMap);
}
private:
TreeNode* buildTreeRecursive(vector<int>& inorder, int inStart, int inEnd,
vector<int>& postorder, int postStart, int postEnd,
unordered_map<int, int>& inorderMap) {
// Base case: if there are no elements to construct the tree
if (inStart > inEnd || postStart > postEnd) {
return nullptr;
}
// The last element in postorder is the root of the tree/subtree
int rootVal = postorder[postEnd];
TreeNode* root = new TreeNode(rootVal);
// Get the index of the root in the inorder array
int inorderIndex = inorderMap[rootVal];
int leftTreeSize = inorderIndex - inStart;
// Recursively build the left and right subtrees
root->left = buildTreeRecursive(inorder, inStart, inorderIndex - 1,
postorder, postStart, postStart + leftTreeSize - 1, inorderMap);
root->right = buildTreeRecursive(inorder, inorderIndex + 1, inEnd,
postorder, postStart + leftTreeSize, postEnd - 1, inorderMap);
return root;
}
};
26.17MB, 9ms
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[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
// Helper function to recursively build the tree
const build = (inStart, inEnd, postStart, postEnd) => {
if (inStart > inEnd || postStart > postEnd) {
return null;
}
// The last element in postorder is the root of the current subtree
const rootVal = postorder[postEnd];
const root = new TreeNode(rootVal);
// Find the index of the root value in the inorder array
const inorderIndex = inorderIndexMap[rootVal];
const leftTreeSize = inorderIndex - inStart;
// Recursively build the left and right subtrees
root.left = build(inStart, inorderIndex - 1, postStart, postStart + leftTreeSize - 1);
root.right = build(inorderIndex + 1, inEnd, postStart + leftTreeSize, postEnd - 1);
return root;
};
// Create a map to store the index of each value in the inorder array for quick lookup
const inorderIndexMap = {};
for (let i = 0; i < inorder.length; i++) {
inorderIndexMap[inorder[i]] = i;
}
return build(0, inorder.length - 1, 0, postorder.length - 1);
};
54.54MB, 83ms
