Comment on page

106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

题目地址

题目描述

Given inorder and postorder traversal of a tree, construct the binary tree.
​
Note:
You may assume that duplicates do not exist in the tree.
​
For example, given
​
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
​
3
/ \
9 20
/ \
15 7

代码

Approach #1 Recursion

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int post_idx;
int[] postorder;
HashMap<Integer, Integer> idx_map = new HashMap();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
post_idx = postorder.length - 1;
​
int idx = 0;
for (Integer val: inorder) {
idx_map.put(val, idx++);
}
return helper(0, inorder.length - 1);
}
​
public TreeNode helper(int in_left, int in_right) {
if (in_left > in_right) { // inorder的作用
return null;
}
​
int root_val = postorder[post_idx];
TreeNode root = new TreeNode(root_val);
​
int index = idx_map.get(root_val); // inorder的作用
​
post_idx--;
root.left = helper(in_left, index - 1);
root.right = helper(index + 1, in_right);
​
return root;
}
}