LeetCode - Construct Binary Tree from Inorder and Postorder Traversal | Darren's Blog

Given inorder and postorder traversal of a tree, construct the binary tree

public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (postorder == null || inorder == null ||

                postorder.length != inorder.length || postorder.length == 0)

            return null;

        return recursiveBuildTree(postorder, 0, inorder, 0, postorder.length);

    }

 

    /**

     * Recursively build binary tree from postorder traversal and inorder traversal with given begining

     * indices of beginning nodes and effective number of nodes

     * @param postorder postorder traversal

     * @param postBegin index of the beginning node in the postorder traversal

     * @param inorder inorder traversal

     * @param inBegin index of the begining node in the inorder traversal

     * @param len number of nodes for both traversal

     * @return

     */

    private TreeNode recursiveBuildTree(int[] postorder, int postBegin, int[] inorder, int inBegin, int len) {

        assert postBegin+len <= postorder.length;

        assert inBegin+len <= inorder.length;

 

        if (len <= 0)       // Empty tree

            return null;

 

        // The beginning node in the preorder traversal is the root

        TreeNode root = new TreeNode(postorder[postBegin+len-1]);

 

        // Find the position of the root in the inorder traversal so as to decide the number of nodes

        // in its left subtree

        int leftTreeLen = 0;

        for(; leftTreeLen < len && inorder[inBegin+leftTreeLen] != root.val; leftTreeLen++);

 

        // Recursively build its left subtree and right subtree; note the change in postBegin, inBegin, and len

        TreeNode left = recursiveBuildTree(postorder, postBegin, inorder, inBegin, leftTreeLen);

        TreeNode right = recursiveBuildTree(postorder, postBegin+leftTreeLen, inorder, inBegin+leftTreeLen+1,

                len-leftTreeLen-1);

 

        // Link the left and right subtrees with the root

        root.left = left;

        root.right = right;

 

        return root;

    }

Read full article from LeetCode - Construct Binary Tree from Inorder and Postorder Traversal | Darren's Blog