Share my java recursion solution; Beat 78%; 6ms


  • 0
    H

    This Post is very helpful.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        HashMap<Integer, Integer> hash = new HashMap<Integer,Integer>();
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            for(int i=0; i<inorder.length; i++) hash.put(inorder[i],i);
            return helper(postorder, postorder.length-1, inorder, 0, inorder.length-1);
        }
        public TreeNode helper(int[] postorder, int root, int[] inorder, int start, int end){
            if(start>end) return null;
            if(root<0) return null;
            
            int rootval = postorder[root];
            int index = hash.get(rootval);
            TreeNode node = new TreeNode(rootval);
            node.right = helper(postorder, root-1, inorder, index+1, end);
            node.left = helper(postorder, root-1-(end-index), inorder, start, index-1);
            return node;
        }
    }
    

Log in to reply
 

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