xqxls

分类

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

/ 注册

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

297篇文章 4409人学习

全部文章（共248篇）

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

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

Java

2022-02-02

0 492

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

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

Java

2022-01-31

0 337

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

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

Java

2022-01-30

0 462

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

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

Java

2022-01-29

0 441

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

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

Java

2022-01-29

0 794

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

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

Java

2022-01-29

0 773

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

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

Java

2022-01-29

0 522

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

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

Java

2022-01-29

0 335

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

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

Java

2022-01-29

0 407

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

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

Java

2022-01-29

0 387