Question

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

105. Construct Binary Tree from Preorder and Inorder Traversal

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

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


For example, given
    preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7


@tag-tree

Algorithm

Since the first in the order of preorder must be the root, the root node of the original binary tree can be known. A very critical condition is given in the title that there are no identical elements in the tree.

With this condition, it can be traversed in the middle order. Locate 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

Note

The pitfall is that I traverse the inorder and find the position of root

  • But pre.length/2 is wrong, the midpoint is not necessarily directly divided by 2, because the binary tree may not be left-right balanced
  • So find root from preorder, and then find root in inorder. In inorder, the ones before root are all children on the left

Code

Java

import java.util.Arrays;

public class Construct_Binary_Tree_from_Preorder_and_Inorder_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[] preorder, int[] inorder) {

            return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }

        TreeNode buildTree(int[] preorder, int pLeft, int pRight, int[] inorder, int iLeft, int iRight) {
            if (pLeft > pRight || iLeft > iRight) return null;

            int i = 0;
            for (i = iLeft; i <= iRight; ++i) {
                if (preorder[pLeft] == inorder[i]) break;
            }

            TreeNode cur = new TreeNode(preorder[pLeft]);

            cur.left = buildTree(preorder, pLeft + 1, pLeft + (i - iLeft), inorder, iLeft, i - 1);
            cur.right = buildTree(preorder, pLeft + (i - iLeft) + 1, pRight, inorder, i + 1, iRight);
            return cur;
        }
    }
}

All Problems

All Solutions