重建二叉树

1. 题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

2. 思路

先序遍历找到root，中序遍历中根据root切分为左子树和右子树

3. 实现

• java

public class 重建二叉树
{
    public TreeNode reConstructBinaryTree(int[] pre, int[] in)
    {
        //检查参数
        if (pre == null || in == null || pre.length != in.length || pre.length == 0 || in.length == 0)
        {
            return null;
        }
        //从pre中取出第一个节点作为root
        TreeNode root = new TreeNode(pre[0]);
        //在in中定位root的位置rootIdx，rootIdx左边为左子树，rootIdx右边为右子树
        int rootIdx = this.getIndexFromArray(in, pre[0]);
        root.left = this.reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIdx + 1), Arrays.copyOfRange(in, 0, rootIdx));
        //在pre中也根据定位划分为左子树和右子树
        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
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param pre int整型一维数组
 * @param vin int整型一维数组
 * @return TreeNode类
 */
func reConstructBinaryTree(pre []int, vin []int) *TreeNode {
	if len(pre) == 0 || len(vin) == 0 {
		return nil
	}
	//从pre中找到root
	rootVal := pre[0]
	root := &TreeNode{
		Val: rootVal,
	}
	//用root把vin分成两半
	var i int
	for i = 0; i < len(vin); i++ {
		if vin[i] == rootVal {
			break
		}
	}
	leftVin := vin[:i]
	rightVin := vin[i+1:]

	//也把pre分成两半
	leftPre := pre[1:i+1]
	rightPre := pre[i+1:]

	//左子树
	root.Left = reConstructBinaryTree(leftPre, leftVin)
	//右子树
	root.Right = reConstructBinaryTree(rightPre, rightVin)
	return root
}

4. 参考

• 重建二叉树_牛客网