冷意

分类

/ 注册

全部文章（共170篇）

题解 | 输出二叉树的右视图

1、解题思路重建二叉树：前序遍历的第一个元素是根节点。在中序遍历中找到根节点的位置，左侧是左子树，右侧是右子树。递归构建左子树和右子树。获取右视图：使用层序遍历（BFS），记录每一层的最后一个节点即为右视图节点。2、代码实现C++ #include <ios> #include <...

2025-06-27

0 40

题解 | 重建二叉树

1、解题思路前序遍历：根节点 -> 左子树 -> 右子树。中序遍历：左子树 -> 根节点 -> 右子树。重建步骤：前序遍历的第一个元素是根节点。在中序遍历中找到根节点的位置，左侧是左子树，右侧是右子树。递归构建左子树和右子树。2、代码实现C++ /** * struct T...

2025-06-26

0 42

题解 | 序列化二叉树

1、解题思路层序遍历（BFS）序列化：使用队列进行层序遍历。节点值之间用逗号分隔，空节点用 # 表示。层序遍历反序列化：将字符串按逗号分割成节点列表。使用队列重建二叉树，依次处理每个节点。2、代码实现C++ /* struct TreeNode { int val; struct T...

2025-06-26

0 26

题解 | 在二叉树中找到两个节点的最近公共祖先

1、解题思路递归遍历：从根节点开始递归遍历二叉树。如果当前节点是 o1 或 o2，则返回当前节点。否则，递归遍历左子树和右子树。如果左右子树都返回非空节点，则当前节点是LCA。如果只有一个子树返回非空节点，则返回该节点。复杂度分析：时间复杂度：O(n)，每个节点最多访问一次。空间复杂度：O(h)...

2025-06-26

0 37

题解 | 二叉搜索树的最近公共祖先

1、解题思路BST的性质：左子树的所有节点值小于当前节点值。右子树的所有节点值大于当前节点值。LCA的性质：如果 p 和 q 分别位于当前节点的左右子树中，则当前节点就是它们的LCA。如果 p 或 q 等于当前节点，则当前节点就是它们的LCA。如果 p 和 q 都小于当前节点值，则LCA在左子树中。...

2025-06-26

0 27

题解 | 判断是不是平衡二叉树

1、解题思路自底向上的递归：从叶子节点开始计算每个节点的高度。在计算高度的同时，检查左右子树的高度差是否超过1。如果超过1，则直接返回不平衡的结果，避免重复计算。复杂度优化：传统自顶向下递归会重复计算子树高度，时间复杂度为 O(n^2)。自底向上递归只需计算一次树高，时间复杂度为 O(n)。2、代码...

2025-06-26

0 26

题解 | 判断是不是完全二叉树

1、解题思路层序遍历（BFS）：使用队列进行层序遍历。检查是否存在某个节点为空后，后面还有非空节点。标记法：在层序遍历时，标记第一次遇到空节点的情况。如果在标记后还遇到非空节点，则不是完全二叉树。2、代码实现C++ /** * struct TreeNode { * int val; * ...

2025-06-26

0 28

题解 | 判断是不是二叉搜索树

1、解题思路递归方法（中序遍历验证）：二叉搜索树的中序遍历结果是一个严格递增的序列。进行中序遍历，记录前一个节点的值，确保当前节点的值大于前一个节点的值。递归方法（上下界验证）：每个节点都有一个值的上下界限制。左子树的所有节点值必须小于当前节点值（上界为当前节点值）。右子树的所有节点值必须大于当...

2025-06-26

0 34

题解 | 二叉树的镜像

1、解题思路递归方法：从根节点开始，递归交换每个节点的左右子树。递归终止条件是当前节点为空。迭代方法（BFS或DFS）：使用栈或队列遍历二叉树。每次取出一个节点，交换其左右子树。将子节点加入栈或队列继续处理。2、代码实现C++（递归） /** * struct TreeNode { * int...

2025-06-26

0 21

题解 | 合并二叉树

1、解题思路递归方法：从两棵树的根节点开始递归合并。如果两个节点都存在，创建一个新节点，值为两节点值之和。递归合并左子树和右子树。如果其中一个节点为空，直接返回另一个节点。迭代方法（BFS或DFS）：使用队列或栈同时遍历两棵树。每次取出两个树的对应节点，按照规则合并。将合并后的节点的子节点加入队列或...

2025-06-26

0 27