[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal [LeetCode] Construct Bina

链接:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ 难度:Medium 题目:105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

翻译:给定树的前序和中序遍历,构造二叉树。 注意: 树中不存在重复项。

思路:首先,你应该知道

前序遍历:根节点,左子树,右子树; 中序遍历:左子树,根节点,右子树;

所以,我们可以从preorder中找到整棵树的根节点,即为preorder[0],由于preorderinorder是对同一棵树的遍历,我们可以知道preorder[0]inorder中一定也存在,不妨设preorder[0]==inorder[k]

由于inorder是中序遍历,所以k左边的就是根节点左子树的中序遍历、k右边的就是根节点右子树的中序遍历。

并且,我们已经知道了根节点左子树的节点数(与中序遍历长度相同),不妨设为l,我们可以知道preorder从1l+1就是根节点左子树的前序遍历,剩下的最后一部分就是根节点右子树的前序遍历。

由此,我们可以计算出左子树、右子树的前序遍历和中序遍历,从而可以用分治的思想,将规模较大的问题分解成为两个较小的问题,然后递归的进行处理,还原左子树和右子树,最后连通根节点一起组成一棵完整的树。

参考代码: Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
        for(int i=0; i<inorder.length; i++)
            inorderMap.put(inorder[i],i);
        return buildTree(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, inorderMap);
    }

    public TreeNode buildTree(int[] preorder, int pLeft, int pRight, int[] inorder, int iLeft, int iRight, Map<Integer,Integer> inorderMap){
        if(pLeft>pRight || iLeft>iRight)
            return null;
        TreeNode cur = new TreeNode(preorder[pLeft]);
        //int i=0;
        //for(i=iLeft; i<= iRight; i++)
        //    if(preorder[pLeft] == inorder[i])
        //        break;
        int i = inorderMap.get(preorder[pLeft]);

        cur.left = buildTree(preorder, pLeft+1, pLeft+i-iLeft, inorder, iLeft, i-1, inorderMap);
        cur.right = buildTree(preorder, pLeft+i-iLeft+1, pRight, inorder, i+1, iRight, inorderMap);
        return cur;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏本立2道生

亚像素数值极值检测算法总结

在计算机视觉领域,经常需要检测极值位置,比如SIFT关键点检测、模板匹配获得最大响应位置、统计直方图峰值位置、边缘检测等等,有时只需要像素精度就可以,有时则需要...

14820
来自专栏自然语言处理

深度 | 朴素贝叶斯模型算法研究与实例分析

本节介绍朴素贝叶斯分类算法模型在中文领域中的应用。我们对新闻语料进行多文本分类操作,本文选择艺术、文学、教育、哲学、历史五个类别的训练文本,然后采用新的测试语料...

19420
来自专栏自然语言处理

实现 | 朴素贝叶斯模型算法研究与实例分析

构建一个快速过滤器来屏蔽在线社区留言板上的侮辱性言论。如果某条留言使用了负面或者侮辱性的语言,那么就将该留言标识为内容不当。对此问题建立两个类别: 侮辱类和非侮...

26240
来自专栏会跳舞的机器人

ZooKeeper典型应用场景一览(转)

ZooKeeper是一个高可用的分布式数据管理与系统协调框架。基于对Paxos算法的实现,使该框架保证了分布式环境中数据的强一致性,也正是基于这样的特性,使得Z...

12310
来自专栏ppjun专栏

排序算法

12320
来自专栏本立2道生

伪随机数生成算法

伪随机数生成算法在计算机科学领域应用广泛,比如枪击游戏里子弹命中扰动、数据科学里对样本进行随机采样、密码设计、仿真领域等等,背后都会用到伪随机数生成算法。

60720
来自专栏Winter漫聊技术

一个随机播放的算法II

音乐时光? 骑着车,戴着耳机,播放列表里有几首歌。 突然,很想听《且听风吟》,但是不想掏出手机,于是一路双击耳机播放键切歌。 emmm,下面是切过的歌:

16930
来自专栏和蔼的张星的图像处理专栏

暗通道去雾算法原理及实现

基本原理来源于何凯明大神的CVPR09的论文Single Image Haze Removal Using Dark Channel Prior

1.5K30
来自专栏自然语言处理

理论 | 朴素贝叶斯模型算法研究与实例分析

朴素贝叶斯是一种构建分类器的简单方法。该分类器模型会给问题实例分配用特征值表示的类标签,类标签取自有限集合。所有朴素贝叶斯分类器都假定样本每个特征与其他特征都不...

15050
来自专栏技术小站

吴恩达深度学习笔记 3.1~3.11 浅层神经网络

神经网络的结构与逻辑回归类似,只是神经网络的层数比逻辑回归多了一层,多出的中间一层叫隐藏层,那么,神经网络的计算就相当于多进行一次逻辑回归的计算

18420

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励