106. Construct Binary Tree from Inorder and Postorder Traversal

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Code

654

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || inorder.length != postorder.length) return null;

        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }

        return helper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, map);
    }

    private TreeNode helper(int[] inorder,
                            int[] postorder,
                            int inStart,
                            int inEnd,
                            int postStart,
                            int postEnd,
                            HashMap<Integer, Integer> map){

        if(inStart > inEnd || postStart < 0){
            return null;
        }

        int rootIndex = map.get(postorder[postEnd]);
        TreeNode root = new TreeNode(postorder[postEnd]);

        root.left = helper(inorder, postorder,
                        inStart,
                        rootIndex - 1,
                        postStart,
                        postStart + rootIndex - inStart - 1,
                        map);

        root.right = helper(inorder, postorder,
                        rootIndex + 1,
                        inEnd,
                        postStart + rootIndex - inStart,
                        postEnd - 1,
                        map);

        return root;
    }
}