xqxls

分类

二叉树技巧总结(2) 未归档(3) 题解(292)

/ 注册

TA的专栏 297篇文章 4人订阅

297篇文章 4446人学习

全部文章（共297篇）

二叉树总结（三）来自专栏

1.技巧描述对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如建立辅助函数、用迭代代替递归、分情况讨论、预置标记变量。建立辅助函数：有时候一个大问题不好解决，但是先解决掉其中一个关键问题，后续就比较好办了。比如要判断A树中是否包含与B树完全相同的子树...

2022-02-07

0 413

二叉树总结（二）来自专栏

1.技巧描述对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如剪枝、预处理、回溯。剪枝：提前排除掉不合法的情况。预处理：比如对要处理的数据提前做哈希映射，或者计算前缀和、后缀和等等。具体情况具体分析。回溯：通过特定的方式，回到上一层递归的...

2022-02-07

0 465

二叉树总结（一）来自专栏

1.技巧描述对于二叉树的问题，一般会采用深度优先搜索和广度优先搜索等方法来解决。深度优先搜索：深度优先搜索会沿着某一条路一直往前走，直到走完这条路为止，有点类似不撞南墙不回头，一般使用递归来实现。广度优先搜索：广度优先搜索会考虑所有可能的路径，每次往前走一步，都相当于在上一步的基础上进...

2022-02-07

0 406

题解 | #二叉树根节点到叶子节点和为指定值的路径# 来自专栏

方法一（深度优先搜索） 1.题意整理给定一颗二叉树以及一个整数sum，二叉树中每个节点对应一个节点值。找出二叉树中所有的从根节点到叶子节点的节点值之和等于sum的路径。 2.思路整理可以利用深度优先搜索，遍历所有可能的路径，然后看某个路径的和是否等于sum，如果存在这样的路径，则加入到结果...

Java

2022-02-03

0 436

题解 | #二叉树的镜像# 来自专栏

方法一（递归） 1.题意整理给定一颗二叉树。求该二叉树的镜像。 2.思路整理递归结束条件：当前节点为空。递归如何传递：每次需要交换当前节点的左子节点和右子节点，然后依次往左子树方向递归、往右子树方向递归。递归的返回值：每次返回当前节点。图解展示： 3.代码实现 import j...

Java

2022-02-03

0 428

题解 | #二叉树的中序遍历# 来自专栏

方法一（栈） 1.题意整理给定一颗二叉树。按照中序打印二叉树中所有的节点。 2.思路整理简单分析：先序遍历的顺序是根、左、右，中序遍历的顺序是左、根、右，后序遍历的顺序是左、右、根。如果直接按照递归的思路进行遍历，只需在对应的位置将当前节点加入到序列即可。比如中序遍历： List&l...

Java

2022-02-02

0 508

题解 | #输出二叉树的右视图# 来自专栏

方法一（递归+BFS） 1.题意整理给定一颗二叉树的前序遍历序列和中序遍历序列。打印出二叉树的右视图。 2.思路整理重建二叉树：一个朴素的思路是，先找到前序序列的第一个元素，将其作为头节点，然后通过遍历中序序列，找到中序序列对应的头节点位置，则中序序列中该位置之前的一定是当前节点的左子树...

Java

2022-01-31

0 359

题解 | #合并二叉树# 来自专栏

方法一（递归） 1.题意整理给定两颗二叉树，将它们合并为一颗二叉树。合并规则是：都存在的节点，就将节点值加起来，否则空的位置就由另一颗树的节点来代替。 2.思路整理只需利用递归确定合并之后的树的每一个节点值。如果其中一棵树的当前节点为空，直接返回另一颗树的节点。如果均不为空，则将当前的两个...

Java

2022-01-30

0 480

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

方法一（递归） 1.题意整理给定一颗二叉树，以及这个二叉树上两个节点对应的值o1和o2。找到该树中o1、o2节点最近的公共祖先。 2.思路整理可以试图遍历整颗二叉树，判断以当前节点为根的子树的左右子树上是否包含o1和o2，如果左右子树一边一个，则当前节点就是公共祖先。如果全在左子树，则左子...

Java

2022-01-29

0 461

题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树# 来自专栏

方法一（递归+广度优先搜索） 1.题意整理给定一颗二叉树，树中没有重复节点。判断该树是否是二叉搜索树、是否是完全二叉树。 2.思路整理判断搜索二叉树（BST）：考虑搜索二叉树的定义，每一个节点的值应该大于等于左子树中的最大值，小于等于右子树中的最小值。所以我们可以利用递归遍历每一个节点，...

Java

2022-01-29

0 814