xqxls

分类

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

/ 注册

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

297篇文章 4446人学习

全部文章（共297篇）

题解 | #判断t1树中是否有与t2树完全相同的子树# 来自专栏

方法一（递归） 1.题意整理给定彼此独立的两棵二叉树t1和t2，树中节点各不相同。判断t2是否是t1的子树。 2.思路整理首先定义一个函数，用来判断两颗树是否完全相同。然后根据这个函数，通过递归的方式遍历t1中所有的子树，看有没有和t2完全相同的。递归终止条件：如果root1、root...

Java

2022-01-29

0 809

题解 | #实现二叉树先序，中序和后序遍历# 来自专栏

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

Java

2022-01-29

0 536

题解 | #序列化二叉树# 来自专栏

方法一（BFS） 1.题意整理实现两个函数，分别用来序列化和反序列化二叉树。序列化是指将二叉树按照某种遍历方式保存为字符串。反序列化是指根据序列化之后的字符串，重建二叉树。 2.思路整理序列化：按照广度优先遍历的思路，首先将根节点入队，然后每次弹出当前节点，如果为空，说明不存在左右子节点...

Java

2022-01-29

0 353

题解 | #按之字形顺序打印二叉树# 来自专栏

方法一（BFS） 1.题意整理给定一颗二叉树。求二叉树的之字形遍历。之字形遍历是指第一层从左到右，第二层从右到左，一直这样交替。 2.思路整理这题和二叉树的层序遍历非常相似，可以利用广度优先搜索来做。唯一不同的是，遇到偶数层的时候，需要对该层所有元素进行反转操作，然后再加入到结果集中。 ...

Java

2022-01-29

0 424

题解 | #对称的二叉树# 来自专栏

方法一（递归） 1.题意整理给定一颗二叉树。判断其是否是自己的镜像。 2.思路整理首先考虑二叉树是否为空，如果为空，则说明是对称的，直接返回true。否则递归地判断左右子树是否是对称的。递归终止条件：如果左右子树同时为空，说明所有子树都满足要求，返回true。如果左子树为空，右子树不为...

Java

2022-01-29

0 404

题解 | #重建二叉树# 来自专栏

方法一（递归+哈希表） 1.题意整理给定一颗二叉树的前序遍历序列和中序遍历序列。重建该二叉树，并返回头节点。 2.思路整理因为前序遍历是按根、左、右的顺序访问节点，中序遍历是按左、根、右的顺序访问节点。一个朴素的思路是，先找到前序序列的第一个元素，将其作为头节点，然后通过遍历中序序列，找到...

Java

2022-01-28

0 382

题解 | #二叉树中和为某一值的路径(二)# 来自专栏

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

Java

2022-01-28

0 447

题解 | #判断是不是平衡二叉树# 来自专栏

方法一（递归+剪枝） 1.题意整理给定一颗二叉树。判断该二叉树是否是平衡二叉树。如果一颗二叉树是空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，则这颗二叉树是平衡二叉树。 2.思路整理一个朴素的想法是，先利用递归计算树中每颗子树的高度，然后再根据子树高度差...

Java

2022-01-28

0 404

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

方法一（BFS） 1.题意整理给定一颗二叉树。求二叉树的层序遍历。 2.思路整理广度优先搜索的过程一般是将源节点入队，然后将当前节点出队，同时找到所有可到达的节点再次入队。循环这个过程，直到遍历完所有的节点。二叉树的层序遍历是一种特殊的广度优先搜索，当前队列中节点的个数即为当前层中节点数目...

Java

2022-01-28

0 613

题解 | #二叉树的最大深度# 来自专栏

方法一（递归） 1.题意整理给定一颗二叉树。求二叉树的最大深度。深度是指树的根节点到任一叶子节点路径上节点的数量。 2.思路整理按照二叉树递归的套路，需要考虑当前节点的情况、当前节点左子树的情况、当前节点右子树的情况。只要知道当前节点左右子树的深度，那么当前节点为根的子树的深度即为两者中较...

Java

2022-01-28

0 348