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

2024-02-21 22:20

本文主要是介绍LeetCode.105. 从前序与中序遍历序列构造二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

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

分析

这道题是告诉我们一颗二叉树的前序和中序,让我们根据前序和中序构造出整颗二叉树。

拿到这道题,我们首先要知道前序的中序又怎样的性质:

  • 前序:【根 左 右】
  • 中序:【左 根 右】

根据以上的性质,我们可以得到以下的结论:

  • 前序遍历的第一个元素一定为数的根节点node的值。
  • 因为题目告诉了我们无重复元素,所以在中序遍历中找到根节点 node 的索引,可以将 中序遍历的数组 划分为 [左子树 | 根节点 | 右子树] 的形式。
  • 在中序遍历数组中我们可以知道以 node 为根节点,左右子树的节点个数,利用这点可以将 前序遍历数组 划分为 [根节点 | 左子树 | 右子树]。
  • 通过上面我们可以知道整颗树的树根,左子树,右子树。下面需要分别构建左子树、右子树,还是按照上面的逻辑。

接下来的问题就是需要知道构建左子树和右子树的时候的前序序列和中序序列。

  • 根节点的值为 preorder[0],然后在中序序列中找到这个节点下标为 inorderIndex
  • 构建左子树:

左子树的 preorder:[1,inorderIndex + 1)
左子树的 inorder :[0,inorderIndex )

  • 构建右子树:

右子树的 preorder:[inorderIndex+1,preorder.length)
右子树的 inorder :[inorderIndex+1,inorder.length)

下面我来举个例子:
在这里插入图片描述

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length == 0) return null;int rootValue = preorder[0];int inorderIndex = -1;for(int i = 0;i < inorder.length;i ++) {if(inorder[i] == rootValue) {inorderIndex = i;break;}}TreeNode rootNode = new TreeNode(rootValue);rootNode.left = buildTree(Arrays.copyOfRange(preorder,1,inorderIndex+1),Arrays.copyOfRange(inorder,0,inorderIndex));rootNode.right = buildTree(Arrays.copyOfRange(preorder,inorderIndex+1,preorder.length),Arrays.copyOfRange(inorder,inorderIndex+1,inorder.length));return rootNode;}
}

在这里插入图片描述

这篇关于LeetCode.105. 从前序与中序遍历序列构造二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/733251

相关文章

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

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

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

day-50 求出最长好子序列 I

思路 二维dp,dp[i][h]表示nums[i] 结尾,且有不超过 h 个下标满足条件的最长好子序列的长度(0<=h<=k),二维数组dp初始值全为1 解题过程 状态转换方程: 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注

用Python实现时间序列模型实战——Day 14: 向量自回归模型 (VAR) 与向量误差修正模型 (VECM)

一、学习内容 1. 向量自回归模型 (VAR) 的基本概念与应用 向量自回归模型 (VAR) 是多元时间序列分析中的一种模型,用于捕捉多个变量之间的相互依赖关系。与单变量自回归模型不同,VAR 模型将多个时间序列作为向量输入,同时对这些变量进行回归分析。 VAR 模型的一般形式为: 其中: ​ 是时间  的变量向量。 是常数向量。​ 是每个时间滞后的回归系数矩阵。​ 是误差项向量,假

时间序列|change point detection

change point detection 被称为变点检测,其基本定义是在一个序列或过程中,当某个统计特性(分布类型、分布参数)在某时间点受系统性因素而非偶然因素影响发生变化,我们就称该时间点为变点。变点识别即利用统计量或统计方法或机器学习方法将该变点位置估计出来。 Change Point Detection的类型 online 指连续观察某一随机过程,监测到变点时停止检验,不运用到

C++中类的构造函数调用顺序

当建立一个对象时,首先调用基类的构造函数,然后调用下一个派生类的 构造函数,依次类推,直至到达派生类次数最多的派生次数最多的类的构造函数为止。 简而言之,对象是由“底层向上”开始构造的。因为,构造函数一开始构造时,总是 要调用它的基类的构造函数,然后才开始执行其构造函数体,调用直接基类构造函数时, 如果无专门说明,就调用直接基类的默认构造函数。在对象析构时,其顺序正好相反。