Question

Formatted question description: https://leetcode.ca/all/106.html

106. Construct Binary Tree from Inorder and Postorder Traversal

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

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

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

@tag-tree

Algorithm

The last one in the post-order sequence must be the root, so the root node of the original binary tree can be known. A very key condition is given in the title that there are no identical elements in the tree.

With this condition, we can also locate in the in-order traversal to find the position of the root node, and split the in-order traversal into the left and right parts according to the position of the root node, and call the original function on it recursively

Code

Java

import java.util.Arrays;

public class Construct_Binary_Tree_from_Inorder_and_Postorder_Traversal {

	/**
	 * Definition for binary tree
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */

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

            return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
        }
        TreeNode buildTree(int[] inorder, int iLeft, int iRight, int[] postorder, int pLeft, int pRight) {
            if (iLeft > iRight || pLeft > pRight) return null;
            TreeNode cur = new TreeNode(postorder[pRight]);
            int i = 0;
            for (i = iLeft; i < inorder.length; ++i) {
                if (inorder[i] == cur.val) break;
            }
            cur.left = buildTree(inorder, iLeft, i - 1, postorder, pLeft, pLeft + (i - iLeft - 1));
            cur.right = buildTree(inorder, i + 1, iRight, postorder, pLeft + (i - iLeft), pRight - 1); // (i - iLeft) is (i - iLeft - 1 + 1)
            return cur;
        }
	}
}

All Problems

All Solutions