Construct Binary Tree from Inorder and Postorder Traversal

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

You may assume that duplicates do not exist in the tree.

Example:

Given inorder [1,2,3] and postorder [1,3,2], return a tree:

  2
 / \
1   3

Solution:

Same approach with Construct Binary Tree from Preorder and Inorder Traversal.

Code:

 public class Solution {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length - 1, 
                    postorder, 0, postorder.length - 1);
    }

    private TreeNode buildTree(int[] inorder, int istart, int iend, 
                        int[] postorder, int pstart, int pend) {
        if (istart > iend) {
            return null;
        }
        int val = postorder[pend];
        int idx = findInorder(inorder, istart, iend, val);
        TreeNode node = new TreeNode(val);
        int rightTreeSize = iend - idx;
        node.left = buildTree(inorder, istart, idx - 1,
                        postorder, pstart, pend - rightTreeSize - 1);
        node.right = buildTree(inorder, idx + 1, iend,
                        postorder, pend - rightTreeSize, pend - 1);
        return node;
    }

    private int findInorder(int[] inorder, int istart, int iend, int val) {
        for (; istart <= iend; istart++) {
            if (inorder[istart] == val) {
                return istart;
            }
        }
        return -1;
    }
}

results matching ""

    No results matching ""