Concise recursive Java code by making slight modification to the previous problem.


  • 3

    Here I'll show you a comparison of code for Construct Binary Tree from [Problem 105: Preorder and Inorder Traversal][1] and from [Problem 106: Inorder and Postorder Traversal][2].

    Code for Problem 105:

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, 0, inorder, 0, inorder.length - 1);
    }
    
    public static TreeNode helper(int[] preorder, int preStart, int[] inorder, int inStart, int inEnd) {
        if (preStart > preorder.length - 1 || inStart > inEnd)
            return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int target = inStart;
        while (inorder[target] != preorder[preStart]) target++;
        root.left = helper(preorder, preStart + 1, inorder, inStart, target - 1);
        root.right = helper(preorder, preStart + target - inStart + 1, inorder, target + 1, inEnd);
    
        return root;
    }
    

    Code for Problem 106:

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(postorder, postorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    public static TreeNode helper(int[] postorder, int postStart, int[] inorder, int inStart, int inEnd) {
        if (postStart < 0 || inStart > inEnd)
            return null;
        TreeNode root = new TreeNode(postorder[postStart]);
        int target = inStart;
        while (inorder[target] != postorder[postStart]) target++;
        root.left = helper(postorder, postStart - inEnd + target - 1, inorder, inStart, target - 1);
        root.right = helper(postorder, postStart - 1, inorder, target + 1, inEnd);
    
        return root;
    }
    

    Note that the only difference is, for post-order we traverse from the end of postorder and change the way for finding poststart.
    Enjoy :)
    [1]: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
    [2]: http://Inorder%20and%20Postorder%20Traversal


Log in to reply
 

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