[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

简介: 链接:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/难度:Medium题目:105.

链接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;
    }
}
目录
相关文章
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
40 1
Leetcode Minimum Depth of Binary Tree (面试题推荐)
计算树的最小深度 很简单的一道题,只需要遍历一次树,到叶子节点的时候计算一下深度和当前最小深度比较,保存最小值就行。 我在这用了一个全局变量 mindepth。总感觉我这代码写的不够简练,求更精简的方法。
44 0
Leetcode Binary Tree Postorder Traversal(面试题推荐)
非递后续归遍历二叉树,肯定得用到栈。先序遍历很好写,但后续遍历就不是那么容易了。 只需要设置个指针pre,指向最后输出的那个节点就行了,只要判断cur指针指向的是上次输出节点的父节点,且cur无其他未遍历的节点,这个时候就把cur节点输出即可,然后更改pre。原理是要遍历当前节点,其所有子节点都必须遍历完,因为肯定是先左后右,所以只需一个指针保持前一次输出的结果即可。
50 0
Leetcode 236. Lowest Common Ancestor of a Binary Tree
根据LCA的定义,二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点,LCA的定义没什么好解释的,主要是这道题的解法。
36 0
Leetcode 623. Add One Row to Tree
题目很简单,在树的第d层加一层,值为v。递归增加一层就好了。代码如下
45 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2
|
1天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
6 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口