Description
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:
tree
Solution
DFS
注意postorder的指针不要算错了。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return buildTreeRecur(inorder, 0, inorder.length - 1,
postorder, 0);
}
public TreeNode buildTreeRecur(int[] inorder, int is, int ie,
int[] postorder, int ps) {
if (is > ie) {
return null;
}
TreeNode root = new TreeNode(postorder[ps + ie - is]);
int index = search(inorder, is, ie, root.val);
root.left = buildTreeRecur(inorder, is, index - 1
,postorder, ps);
root.right = buildTreeRecur(inorder, index + 1, ie
,postorder, ps + index - is);
return root;
}
public int search(int[] nums, int start, int end, int val) {
while (start <= end && nums[start] != val) {
++start;
}
return start;
}
}
