My 5ms Recursion Java Code With Explanation (Divide and Conquer)


  • 0
    J

    Like the most welcome solution of this question, the idea is every time we choose the last element in postorder array, then target its index in the inorder array(I use HashMap to make this search more efficient and easy to understand). This node is every tree's root(we can treat every subtree as a tree). Then the inorder array are divide into 2 subarray by this node(let's call it pivot). Then we recursion for this two subarray to do the same thing, which is divide and conquer.

    The key point is that we need to record the start position and end position of inorder array and the end position of the postorder array, since they cannot be easily linked to each other. And we need to use the former to know the range of the 2 subtree, and use the latter to make the real root node in every recursion level.

    public class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (postorder.length == 0) {
                return null;
            }
            
            HashMap<Integer, Integer> map = new HashMap<>(); 
            for (int i = 0; i < inorder.length; i++) { 
                map.put(inorder[i], i);
            }
            return buildTree(map, 0, inorder.length - 1, postorder, postorder.length - 1);
        }
        
        private TreeNode buildTree(HashMap<Integer, Integer> map, int inStart, int inEnd, int[] postorder, int poEnd) {//no need poStart
            TreeNode node = new TreeNode(postorder[poEnd]); 
            
            int pivot = map.get(node.val); 
            int leftSize = pivot - inStart; 
            int rightSize = inEnd - pivot;
            
            if (rightSize > 0) { 
                node.right = buildTree(map, pivot + 1, inEnd, postorder, poEnd - 1);
            }
            
            if (leftSize > 0) { 
                node.left = buildTree(map, inStart, pivot - 1, postorder, poEnd - rightSize - 1);
            }
            return node;  
        }
    }

Log in to reply
 

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