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

## 题目地址

https://leetcode.com/problems/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;
}
}``````

Last updated