IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 力扣hot100 105题从前序与中序遍历序列构造二叉树 打卡 -> 正文阅读

[数据结构与算法]力扣hot100 105题从前序与中序遍历序列构造二叉树 打卡

105. 从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历?preorder?与中序遍历??inorder。请构造二叉树并返回其根节点。

示例一:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例二:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder?和?inorder?均无重复元素
inorder?均出现在?preorder
preorder?保证为二叉树的前序遍历序列
inorder?保证为二叉树的中序遍历序列

解题思路:这道题是数据结构笔试的一道常考题,经常会出选择题,我们可以利用前序遍历和中序遍历的性质来完成原二叉树的构建,因为题目告诉了我们每个节点都是不相同的,所以保证了我们构建的二叉树的唯一性。

前序遍历的特点:第一个节点为根节点,所有的左子树节点都在右子树节点之前,如下图所示:

?中序遍历的特点:前半部分为左子树节点,中间为根节点,剩余部分为右子树节点,如下图所示:

?我们可以使用一个哈希表将中序遍历的每一个节点的值及其数组下表存储起来,每次使用前序遍历的第一个节点寻找中序遍历根节点的下表,从而计算出左子树和右子树的长度。从而计算出左子树和右子树先序遍历数组和中序遍历数组进行递归,最后返回根节点即可。

实现代码和提交截图如下图所示:

class Solution {
    HashMap<Integer,Integer> map = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {     
        for(int i = 0 ; i < inorder.length ; i++){
            map.put(inorder[i],i);
        }
        return dfs(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }
    //lp,rp代表递归的先序遍历数组左侧下标及右侧下标,这样可以在原数组上截取新的先序遍历数组。
    //li,ri代表递归的中序遍历数组左侧下标和右侧下标,这样可以在原数组上截取新的中序遍历数组。
    private TreeNode dfs(int[] preorder, int[] inorder , int lp , int rp , int li , int ri){
        if(lp > rp){
            return null;
        }
        TreeNode node = new TreeNode(preorder[lp]);
        int index = map.get(node.val);
        int lsize = index - li;
        int rsize = ri - index;
        //先序的左子树[lp + 1 ,lp + lsize] 右子树[lp + lsize + 1,rp]
        //中序的左子树[li , index - 1] 右子树[index + 1 ,ri]
        node.left = dfs(preorder,inorder,lp + 1,lp + lsize,li,index - 1);
        node.right = dfs(preorder,inorder,lp + lsize + 1,rp,index + 1,ri);
        return node;
    }
}

?总结:二叉树的本身就是一个递归,加油。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-12-14 16:12:59  更:2021-12-14 16:15:28 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 16:22:20-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码