My java Solution with O(n)


  • 0
    E
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            // sanity check
            if (inorder == null || postorder == null || inorder.length != postorder.length || inorder.length == 0) {
                return null;
            }
            Map<Integer, Integer> map = getMap(inorder);
            
            return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, map);
        }
        
        private TreeNode helper(int[] in, int inl, int inr, int[] post, int postl, int postr, Map<Integer, Integer> map) {
            // base case
            if (postl > postr) {
                return null;
            }
            
            //recursive rule
            TreeNode root = new TreeNode(post[postr]);
            int size = map.get(post[postr]) - inl;
            root.left = helper(in, inl, inl + size - 1, post, postl, postl + size - 1, map);
            root.right = helper(in, inl + size + 1, inr, post, postl + size, postr - 1, map);
            return root;
        }
        
        private Map<Integer, Integer> getMap(int[] inorder) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return map;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.