重建二叉树

5.重建二叉树

题目描述

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

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

解题思路

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

代码实现

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))
    }

引用声明

该题目引用自
牛客网