专栏首页小浩算法《剑指offer》第六天:重建二叉树

《剑指offer》第六天:重建二叉树

❝恶魔:说出你的三个愿望! 男:请你实现我的第二个愿望。 恶魔:然后呢? 男:请你实现我的第一个愿望。 恶魔:Exception in thread "main" java.lang.StackOverflowError —— 小浩 ❞

重建二叉树

题目描述

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

原题题目

思路分析

动图展示

原文参考

解法

在二叉树的前序遍历序列中,第一个数字总是根结点的值。在中序遍历序列中,根结点的值在序列的中间,左子树的结点位于根结点左侧,而右子树的结点位于根结点值的右侧。

遍历中序序列,找到根结点,递归构建左子树与右子树。

注意添加特殊情况的 if 判断。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    /**
     * 重建二叉树
     * 
     * @param pre 先序序列
     * @param in  中序序列
     * @return 二叉树根结点
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        int n = pre.length;
        return constructBinaryTree(pre, 0, n - 1, in, 0, n - 1);
    }

    private TreeNode constructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        TreeNode node = new TreeNode(pre[startPre]);
        if (startPre == endPre) {
            if (startIn == endIn) {
                return node;
            }
            throw new IllegalArgumentException("Invalid input!");
        }

        int inOrder = startIn;
        while (in[inOrder] != pre[startPre]) {
            ++inOrder;
            if (inOrder > endIn) {
                new IllegalArgumentException("Invalid input!");
            }
        }
        int len = inOrder - startIn;
        if (len > 0) {
            // 递归构建左子树
            node.left = constructBinaryTree(pre, startPre + 1, startPre + len, in, startIn, inOrder - 1);
        }

        if (inOrder < endIn) {
            // 递归构建右子树
            node.right = constructBinaryTree(pre, startPre + len + 1, endPre, in, inOrder + 1, endIn);
        }
        return node;

    }
}

测试用例

  1. 普通二叉树(完全二叉树;不完全二叉树);
  2. 特殊二叉树(所有结点都没有左/右子结点;只有一个结点的二叉树);
  3. 特殊输入测试(二叉树根结点为空;输入的前序序列和中序序列不匹配)。

我把我写的所有题解整理成了一本电子书放在了 github 上,三天内冲击到 github 排行榜榜首!近 5w 人下载阅读!要获取的话,直接进入下方链接就可以了(记得给我点个 star):

https://github.com/geekxh/hello-algorithm

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:博弈论系列 之 海盗分金币的故事(附:代码实现)

    在面试的过程中,除了常规的算法题目,我们经常也会被问到一些趣味题型来考察思维,尤其以 FLAG(Facebook, LinkedIn, Amazon, Goog...

    程序员小浩
  • 万字长文!位运算面试看这篇就够了!

    祝大家五一快乐。今天是小浩算法 “365刷题计划” 位运算超长 - 整合篇。估计五一期间,大家也没有什么心思好好做题。所以我就把之前已经出过的位运算系列,进行了...

    程序员小浩
  • 漫画:算法如何验证合法数独 | 全世界最难的数独?

    今天是小浩算法 “365刷题计划” 第95天 。数独相信在座的各位都玩过,那我们如何使用程序去验证一个 9×9 的数独是有效的呢?一起看下!

    程序员小浩
  • 【2019领域驱动设计峰会】领域场景驱动设计实战工作坊

    领域场景驱动设计实战工作坊将以事件风暴为纵贯线,以领域场景为横切面,引入场景驱动设计与测试驱动开发完成从领域建模到编码实现的全过程实战。内容涵盖事件风暴、场景驱...

    ThoughtWorks
  • 根据先序和中序求出二叉树的高度

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • HDU 1213 How Many Tables

    How Many Tables Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

    Angel_Kitty
  • 五分钟搞懂什么是B-树(全程图解)【转】

    我们大家都知道动态查找树能够提高查找效率,比如:二叉查找树,平衡二叉查找树,红黑树。他们查找效率的时间复杂度O(log2n),跟树的深度有关系,那么怎么样才能提...

    233333
  • 《Python自然语言处理》答案第一、二章

    第一章 1 12/(4+1) 2 26**100 4 len(text2) len(set(text2)) 7 len(list(nltk.bigrams(te...

    JasonhavenDai
  • 6.3.2 B+树基本概念

    2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

    week
  • PAT 1001 A+B Format (20分) to_string()

    Calculate a+b and output the sum in standard format -- that is, the digits must ...

    vivi

扫码关注云+社区

领取腾讯云代金券