摸鱼学大师

题解

未归档(8)

/ 注册

全部文章 / 题解（共27篇）

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

思路：题目的主要信息：利用二叉树中序遍历结果及先序遍历结果构建一棵二叉树打印二叉树的右视图，即二叉树每层最右边的结点元素节点值互不相同可以发现解这道题，我们有两个步骤：建树打印右视图首先建树方面，先序遍历是根左右的顺序，中序遍历是左根右的顺序，因为节点值互不相同，我们可以根据...

二叉树右视图递归 dfs 层次遍历建树栈

2021-07-24

15 3625

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

思路：题目的主要信息：合并（相加）二叉树位置相同的结点缺少的结点用另一棵树来补，若都缺则返回NULL 方法一：递归先序遍历同时先序遍历两棵树即可完成。具体做法：首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。然后依据先序遍历的特点，根左右的顺序递归访问。 c...

二叉树层次遍历先序遍历递归队列合并二叉树

2021-07-21

0 595

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

思路：题目的主要信息： t1中含有t2的拓扑结构，即t2是t1的子树方法一：先序递归法具体做法：对t1的每个结点递归遍历（先序），寻找是否有这样的子树，而寻找是否有子树的时候也是用递归，但这次是t1与t2同步先序遍历，遍历完一个t2或者有不相等的结点为止。 class Solution...

递归子树二叉树

2021-07-18

1 1170

题解 | #完全二叉树结点数# 来自专栏

思路：最简单的办法莫过于遍历所有的结点，统计个数，但是不管是哪种遍历，时间复杂度都要求至少为O(n)，因为要遍历每一个结点。方法一：遍历法不符合复杂度要求！！！方法二：二分法（利用性质）由此，我们可以从完全二叉树的性质下手：完全二叉树叶子结点只能出现在最下两层最下层的叶子一定集中在左...

二叉树完全二叉树满二叉树递归最大深度

2021-07-16

4 718

题解 | #把二叉树打印成多行# 来自专栏

思路：题目要求将二叉树按行打印，即按层打印，其中每层分开。不难想到，要使用层次遍历，但是难点在于如何每层分开存储，从哪里知晓分开的时机？在层次遍历的时候，我们通常会借助队列（queue）,事实上，队列中的值大有玄机，让我们一起来看看：当根节点进入队列时，队列长度为1，第一层结点数也为1 若是根...

二叉树层次遍历队列递归非递归

2021-07-15

0 580

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

思路：序列化二叉树即找一种顺序存储二叉树的结点，并以相同的方式能够读取序列重新构建。换种说法，就是遍历二叉树，记录每个结点，再以同样的方式遍历就可以还原二叉树。遍历的方法有四种：先序遍历、中序遍历、后序遍历、层次遍历，理论上只要以相同的方式序列化或者反序列化，都可以解题。方法一：先序遍历 ...

二叉树先序遍历序列化反序列化 char数组

2021-07-15

0 519

题解 | #平衡二叉树# 来自专栏

思路：判断某二叉树是否为平衡二叉树，就需要判断任意一结点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则。则可以相当将问题不断分成子问题，使用递归。方法一：递归判断+递归计算深度具体做法：写两个函数，一个递归遍历二叉树所有结点，判断该结点下的子树是否为平衡二叉树，另一个函...

平衡二叉树递归深度二叉树

2021-07-14

0 579