5.重建二叉树

题目描述

根据二叉树的前序遍历和中序遍历的结果,重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

preorder:    1,2,4,7,3,5,6,8
inorder:     4,7,2,1,5,3,8,6

erchashu

解题思路

前序遍历的第一个值为根节点的值,使用这个值将中序遍历结果分成两部分,左部分为树的左子树中序遍历结果,右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。

代码实现

java 代码

/**
 * 二叉树节点
 */
class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    @NonNull
    @Override
    public String toString() {
        return "TreeNode(value=" + value + ",left=" + left + ",right=" + right + ")";
    }
}

/**
 * 根据前序遍历和中序变量重建二叉树
 *
 * @param pre    前序遍历
 * @param middle 中序遍历
 */
private TreeNode reConstructBinaryTree(int[] pre, int[] middle) {
    return reConstructBinaryTree(pre, 0, pre.length - 1, middle, 0, middle.length - 1);
}

/**
 * 根据前序遍历和中序变量重建二叉树
 *
 * @param pre         前序遍历
 * @param preStart    前序遍历开始位置
 * @param preEnd      前序遍历结束位置
 * @param middle      中序遍历
 * @param middleStart 中序遍历开始位置
 * @param middleEnd   中序遍历结束位置
 */
private TreeNode reConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] middle, int middleStart, int middleEnd) {
    if (preStart > preEnd || middleStart > middleEnd) {
        return null;
    }
    TreeNode node = new TreeNode(pre[preStart]);
    for (int i = middleStart; i <= middleEnd; i++) {
        if (pre[preStart] == middle[i]) {
            int leftCount = i - middleStart;
            node.left = reConstructBinaryTree(pre, preStart + 1,preStart+leftCount,middle,middleStart,i-1);
            node.right = reConstructBinaryTree(pre,preStart+leftCount+1,preEnd,middle,i+1,middleEnd);
        }
    }
    return node;
}

public static void main(String[] args){
    
}

Kotlin 代码

/**
 * 二叉树节点
 */
data class TreeNode(val value: Int,var left: TreeNode? = null,var right: TreeNode? = null) 


/**
 * 根据前序遍历和中序变量重建二叉树
 * @param pre 前序遍历
 * @param middle 中序遍历
 */
private fun reConstructBinaryTree(pre: IntArray, middle: IntArray): TreeNode? {
    return reConstructBinaryTree(pre, 0, pre.size - 1, middle, 0, middle.size - 1)
}

/**
 * 根据前序遍历和中序变量重建二叉树
 * @param pre 前序遍历
 * @param preStart 前序遍历开始位置
 * @param preEnd 前序遍历结束位置
 * @param middle 中序遍历
 * @param middleStart 中序遍历开始位置
 * @param middleEnd 中序遍历结束位置
 */
private fun reConstructBinaryTree(
    pre: IntArray,
    preStart: Int,
    preEnd: Int,
    middle: IntArray,
    middleStart: Int,
    middleEnd: Int
): TreeNode? {
    if(preStart>preEnd||middleStart>preEnd){
        return null
    }
    //前序遍历起始值作为当前节点的值
    val node = TreeNode(pre[preStart])
    for (i in middleStart..middleEnd) {
        //找到中序遍历中与前序遍历当前节点值相同的位置i,
        // 则中序遍历中该位置i前的都是左子树,该位置i后的都是右子树
        if (pre[preStart] == middle[i]) {
            //左子树递归
            val leftCount = i - middleStart
            node.left = reConstructBinaryTree(
                pre,
                preStart + 1,
                preStart + leftCount,
                middle,
                middleStart,
                i - 1
            )
            //右子树递归
            node.right = reConstructBinaryTree(
                pre,
                preStart + 1 + leftCount,
                preEnd,
                middle,
                i + 1,
                middleEnd
            )
        }
    }
    return node
}

/**
 * 入口函数
 */
fun main(args: Array<String>) {
    val pre = intArrayOf(1,2,4,7,3,5,6,8)
    val middle = intArrayOf(4,7,2,1,5,3,8,6)
    println(reConstructBinaryTree(pre,middle))
}

引用声明

该题目引用自
牛客网