LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

Problem:

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

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

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int[] inorder, postorder;
    int current;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) return null;
        this.inorder = inorder; this.postorder = postorder;
        current = postorder.length - 1;
        return buildTree(0, inorder.length - 1);
    }
    
    private int findIndex(int post) {
        for (int i = 0; i < inorder.length; i++)
            if (inorder[i] == postorder[post]) return i;
        return -1;
    }
    
    private TreeNode buildTree(int start, int end) {
        if (start > end) return null;
        TreeNode root = new TreeNode(postorder[current]);
        int index = findIndex(current);
        current--;
        root.right = buildTree(index + 1, end);
        root.left = buildTree(start, index - 1);
        return root;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *