105. Construct Binary Tree from Preorder and Inorder Traversal
Tags:
Medium
Skills:
Tree
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đây là một bài toán kinh điển về xây dựng lại binary tree từ mảng: preorder và inorder. Ý tưởng dựa trên tính chất sau
Approach
Solution
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
16 const inorder_index: Map<number, number> = new Map();
17 inorder.forEach((val, idx) => inorder.set(val, idx));
18 let pre_idx = 0;
19
20 function helper(left: number, right: number): TreeNode | null {
21 if(left > right) return null;
22 const root_val = preorder[pre_idx++];
23 const root = new TreeNode(root_val);
24
25 const idx = inorder_idx.get(root_val)!;
26 root.left = helper(left, idx - 1);
27 root.right = helper(idx + 1, right)
28
29 return root
30 }
31
32 return helper(0, inorder.length - 1);
33};