type
status
date
slug
summary
tags
category
icon
password
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
要解决这个问题，我们可以利用先序遍历和中序遍历的性质：
- 在先序遍历中，第一个元素是根节点。
- 在中序遍历中，根节点将数组分为左子树和右子树。
以下是构造二叉树的步骤：
- 从先序遍历数组中取出第一个元素，这个元素是构建树的根节点。
- 在中序遍历数组中找到根节点的位置，这个位置将中序遍历分为左子树和右子树。
- 根据中序遍历中左子树的长度，我们可以在先序遍历中确定左子树的元素范围。
- 递归地对左子树和右子树执行相同的步骤。
112. 路径总和 - 力扣（LeetCode）
‣
200. 岛屿数量 - 力扣（LeetCode）
在C++中，单引号（' '）和双引号（" "）用于不同的目的：
- 单引号（' '）：
- 用于表示字符（Character）常量。
- 一个字符常量由单引号包围，并且只能包含一个字符。
- 例如：
'A'表示字符 'A'，'\n'表示换行符。
- 双引号（" "）：
- 用于表示字符串（String）常量。
- 一个字符串常量由双引号包围，可以包含零个或多个字符。
- 例如：
"Hello, World!"表示字符串 "Hello, World!"。
一些关键点：
- 字符常量在内存中通常占用一个字节，而字符串常量占用的内存大小是字符串长度加一个额外的空字符（'\0'），用于标记字符串的结束。
- 字符常量没有结束的空字符，因此它们的大小是固定的。
- 在C++标准库中，字符串字面量（使用双引号）默认是
const char数组，而字符字面量（使用单引号）是char类型。
101. 对称二叉树
已解答
简单
相关标签
相关企业
给你一个二叉树的根节点
root ， 检查它是否轴对称。示例 1：
示例 2：
在二叉树的对称性检查中，我们需要成对地比较树的左右两侧的节点，而不是将所有节点的值收集到列表中然后检查这个列表是否与其反转相等
547. 省份数量
已解答
中等
相关标签
相关企业
有
n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个
n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。
示例 1：
示例 2：
提示：
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j]为1或0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
与岛屿数量不同！
1254. 统计封闭岛屿的数目
已解答
中等
相关标签
相关企业
提示
二维矩阵
grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。请返回 封闭岛屿 的数目。
示例 1：
示例 2：
示例 3：
提示：
1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1
二叉树中的最大路径和_牛客题霸_牛客网 (nowcoder.com)
描述
二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。
注意:
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点，且不一定经过根节点
给定一个二叉树的根节点root，请你计算它的最大路径和
例如：
给出以下的二叉树，
最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6
数据范围：节点数满足 1≤n≤1051≤n≤105 ，节点上的值满足 ∣val∣≤1000∣val∣≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
示例1
输入：
{1,2,3}复制返回值：
6复制示例2
输入：
{-20,8,20,#,#,15,6}复制返回值：
41复制说明：
其中一条最大路径为:15=>20=>6，路径和为15+20+6=41
示例3
输入：
{-2,#,-3}复制返回值：
-2这个问题是关于二叉树的一个经典问题，即计算二叉树中的最大路径和。最大路径和可以包含任意两个节点，路径上的节点值之和最大。这个问题的关键在于理解，路径可以是任意两个节点之间的，而不一定是根到叶子的路径。
这个问题可以通过深度优先搜索（DFS）来解决，使用递归的方式遍历二叉树的每一个节点。对于每个节点，我们需要计算经过该节点的最大路径和，这包括：
- 该节点本身作为一个路径的和。
- 该节点作为路径的一部分，即从该节点到其左右子树中较大子树的路径和。
由于我们需要计算经过每个节点的最大路径和，我们可以使用一个额外的变量来记录全局的最大路径和。
以下是这个问题的算法步骤：
- 定义一个辅助函数
maxPathSumUtil，它接受当前节点node和全局最大路径和maxSum作为参数。
- 在
maxPathSumUtil函数中，首先计算当前节点的左子树和右子树的最大路径和。
- 如果左子树或右子树为空，将对应的路径和设置为0。
- 计算经过当前节点的最大路径和，即当前节点的值加上左右子树路径和的较大者。
- 更新全局最大路径和
maxSum，如果经过当前节点的路径和加上当前节点的值大于当前的maxSum。
- 返回经过当前节点的最大路径和，这将用于父节点的计算。
以下是这个问题的 Python 代码示例：
请注意，这个代码示例是一个框架，你需要根据实际的输入格式来构建二叉树并调用
maxPathSum 函数。将升序数组转化为平衡二叉搜索树_牛客题霸_牛客网 (nowcoder.com)
或为{0,-1,1,#,#,#,2}，如下图所示：
返回任意一种即可。
示例1
输入：
[-1,0,1,2]复制返回值：
{1,0,2,-1}复制示例2
输入：
[]复制返回值：
{}重建二叉树_牛客题霸_牛客网 (nowcoder.com)
描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：n≤2000n≤2000，节点的值 −10000≤val≤10000−10000≤val≤10000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
示例1
输入：
[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]复制返回值：
{1,2,3,4,#,5,6,#,7,#,#,8}复制说明：
返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示示例2
输入：
[1],[1]复制返回值：
{1}复制示例3
输入：
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]复制返回值：
{1,2,5,3,4,6,7}二叉树的最大深度_牛客题霸_牛客网 (nowcoder.com)
描述
求给定二叉树的最大深度，
深度是指树的根节点到任一叶子节点路径上节点的数量。
最大深度是所有叶子节点的深度的最大值。
（注：叶子节点是指没有子节点的节点。）
数据范围：0≤n≤1000000≤n≤100000，树上每个节点的val满足 ∣val∣≤100∣val∣≤100要求： 空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)
示例1
输入：
{1,2}复制返回值：
2
复制示例2
输入：
{1,2,3,4,#,#,5}复制返回值：
3- 作者:VON
- 链接:https://baisihan.asia/article/d177815b-3bf3-4b65-90e2-728c3dce6773
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。