Construct Binary Tree from Inorder and Postorder Traversal
Analysis:
Mirror problem of Construct Binary Tree from Inorder and Preorder Traversal. Reverse of postorder is root -> right ->left. So start from the end of the postorder array. Have to be extremely careful when dealing with left and right of inorder array.
Solution:
Mirror problem of Construct Binary Tree from Inorder and Preorder Traversal. Reverse of postorder is root -> right ->left. So start from the end of the postorder array. Have to be extremely careful when dealing with left and right of inorder array.
Solution:
/**
* 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) {
Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
return helper(postorder.length - 1, 0, inorder.length - 1, postorder, inMap);
}
private TreeNode helper(int postStart, int inStart, int inEnd, int[] postorder, Map<Integer, Integer> inMap) {
if (inStart > inEnd) return null;
TreeNode root = new TreeNode(postorder[postStart]);
int inIndex = inMap.get(root.val);
root.right = helper(postStart - 1, inIndex + 1, inEnd, postorder, inMap);
root.left = helper(postStart - (inEnd - inIndex + 1), inStart, inIndex - 1, postorder, inMap);
return root;
}
}
评论
发表评论