Reconstruct Binary Tree

1. Problem Description

Given the preorder traversal and inorder traversal results of a binary tree, reconstruct the binary tree. Assume that the input preorder traversal and inorder traversal results contain no duplicate numbers. For example, given preorder traversal sequence {1,2,4,7,3,5,6,8} and inorder traversal sequence {4,7,2,1,5,3,8,6}, reconstruct the binary tree and return it.

2. Approach

Find the root from the preorder traversal, then split the inorder traversal into the left subtree and right subtree according to the root.

3. Implementation

• java

public class 重建二叉树
{
    public TreeNode reConstructBinaryTree(int[] pre, int[] in)
    {
        // Check parameters
        if (pre == null || in == null || pre.length != in.length || pre.length == 0 || in.length == 0)
        {
            return null;
        }
        // Take the first node from pre as the root
        TreeNode root = new TreeNode(pre[0]);
        // Locate the root position rootIdx in in; the left side of rootIdx is the left subtree and the right side is the right subtree
        int rootIdx = this.getIndexFromArray(in, pre[0]);
        root.left = this.reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIdx + 1), Arrays.copyOfRange(in, 0, rootIdx));
        // Split pre into the left subtree and right subtree according to the same position
        root.right = this.reConstructBinaryTree(Arrays.copyOfRange(pre, rootIdx + 1, pre.length), Arrays.copyOfRange(in, rootIdx + 1, in.length));
        return root;


    }

    private int getIndexFromArray(int[] array, int val)
    {
        for (int i = 0; i < array.length; i++)
        {
            if (array[i] == val)
            {
                return i;
            }
        }

        return -1;
    }
}

• go

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @param pre one-dimensional int array
 * @param vin one-dimensional int array
 * @return TreeNode class
 */
func reConstructBinaryTree(pre []int, vin []int) *TreeNode {
	if len(pre) == 0 || len(vin) == 0 {
		return nil
	}
	// Find the root from pre
	rootVal := pre[0]
	root := &TreeNode{
		Val: rootVal,
	}
	// Split vin into two parts using root
	var i int
	for i = 0; i < len(vin); i++ {
		if vin[i] == rootVal {
			break
		}
	}
	leftVin := vin[:i]
	rightVin := vin[i+1:]

	// Also split pre into two parts
	leftPre := pre[1:i+1]
	rightPre := pre[i+1:]

	// Left subtree
	root.Left = reConstructBinaryTree(leftPre, leftVin)
	// Right subtree
	root.Right = reConstructBinaryTree(rightPre, rightVin)
	return root
}

4. References

• Reconstruct Binary Tree - NowCoder