剑指offer系列之四:重建二叉树

简介:

题目描述

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

在完成代码之前,我自己分析了一下如何根据前序遍历和中序遍历的结果构建一棵二叉树。首先,根据二叉树遍历的性质,由前序遍历的结果序列可知该二叉树的根节点是1,在根据中序遍历的结果可是根节点1的左子树包含的结点是4、7、2,右子树包含的节点是5、3、8、6。现在考虑左子树中节点4、7、2,由于这三个节点在前序遍历的结果是2、4、7,那么2必然是这三个节点组成的子树的根节点,再回到中序遍历的结果4、7、2,那么可以判断出4是2的左孩子,7是4的右孩子;同理可以对右子树进行判断。这样,画出的二叉树是这样的:

构建的二叉树

自然,我们可以分析判断过程写出构建二叉树的完整代码:

package com.rhwayfun.offer;

public class ConstructBinaryTree {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return constructCore(pre,0,pre.length - 1,in,0,in.length - 1);
    }

    private TreeNode constructCore(int[] pre,int startPreOrder, int endPreOrder, int[] in,int startInOrder, int endInOrder) {
        //根据前序遍历找到根节点的值
        int rootValue = pre[startPreOrder];
        TreeNode rootNode = new TreeNode(rootValue);
        rootNode.left = null;
        rootNode.right = null;

        //只有一个结点,那么该节点就是根节点,直接返回
        if(startPreOrder == endPreOrder){
            if(startInOrder == endInOrder && pre[startPreOrder] == in[startInOrder]){
                return rootNode;
            }
        }

        //根据中序遍历的结果找到根节点
        int rootOfInOrder = startInOrder;
        while(rootOfInOrder <= endInOrder && in[rootOfInOrder] != rootValue){
            rootOfInOrder++;
        }

        //异常处理
        if(rootOfInOrder == endInOrder && in[rootOfInOrder] != rootValue){
            return null;
        }

        //计算左子树的长度
        int leftSubTreeLen = rootOfInOrder - startInOrder;
        //根据左子树的长度计算前序遍历结果中左子树的最后一个结点的下标
        int leftIndexOfPreOrderEnd = startPreOrder + leftSubTreeLen;
        //重建左子树
        if(leftSubTreeLen > 0){
            rootNode.left = constructCore(pre, startPreOrder + 1, leftIndexOfPreOrderEnd, in, startInOrder, rootOfInOrder - 1);
        }
        //重建右子树
        if(leftSubTreeLen < endPreOrder - startPreOrder){
            rootNode.right = constructCore(pre, leftIndexOfPreOrderEnd + 1, endPreOrder, in, rootOfInOrder + 1, endInOrder);
        }
        return rootNode;
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode root = new ConstructBinaryTree().reConstructBinaryTree(pre, in);
        System.out.println(root);
    }
}
目录
相关文章
|
7月前
【一刷《剑指Offer》】面试题 6:重建二叉树
【一刷《剑指Offer》】面试题 6:重建二叉树
|
7月前
|
C++
【剑指offer】-重建二叉树-04/67
【剑指offer】-重建二叉树-04/67
|
存储 C++
【C++从0到王者】第三十站:二叉树的非递归遍历
【C++从0到王者】第三十站:二叉树的非递归遍历
47 0
【洛谷算法题】B2029-大象喝水【入门1顺序结构】
【洛谷算法题】B2029-大象喝水【入门1顺序结构】
|
存储
每日一题——设计单链表
每日一题——设计单链表
【牛客】二叉树遍历
【牛客】二叉树遍历
59 0
|
存储 移动开发
【蓝桥杯集训·每日一题】AcWing 1497. 树的遍历
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 递归
78 0
|
存储 算法
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
|
机器学习/深度学习 C++
【力扣·每日一题】1036. 逃离大迷宫 (C++ bfs 思维)
【力扣·每日一题】1036. 逃离大迷宫 (C++ bfs 思维)
98 0
【力扣·每日一题】1036. 逃离大迷宫 (C++ bfs 思维)