常见算法基础题思路简析(三)-二叉树篇

原创
2017/09/28 22:08
阅读数 244

常见算法基础题思路简析(三)-二叉树篇

标签: algorithms


[TOC]


本文对和 二叉树 有关的常见算法基础题思路分类进行分析和总结,并以 Java 为例,适当指出需要注意的编程细节

判断是否为平衡二叉树

题目见 CheckBalance

思路:

  1. 判断左子树是否为平衡二叉树,是则返回高度,不是返回 -1
  2. 判断右子树是否为平衡二叉树,是则返回高度,不是返回 -1
  3. 若左右子树均时平衡二叉树,则看两者高度差是否大于 1。是则返回 -1,不是则取两者中大的再加上 1

注意:

  • 这里对返回值意义复用了,非负数则表示高度,负数表示不是平衡二叉树

判断是否为完全二叉树

题目见 CheckCompletion

思路:

  1. 使用队列,按层遍历二叉树,分以下几种情况依次判断:
  • 如果只有右孩子,返回 false
  • 如果已经遍历过最后一个非叶子节点,当前节点还是非叶子节点,返回 false
  • 如果左孩子非空,入队
  • 如果右孩子非空,入队;如果右孩子空,表示该节点应为最后一个非叶子节点
  1. 若遍历完,则是完全二叉树

找出搜索二叉树中换位的两个节点

题目见 FindErrorNode

思路:

  1. 中序遍历二叉树,找到出现降序的节点。第一次出现降序的较大值为换位的两个节点中的较大值,最后一次降序的较小值为换位节点中的较小值

注意:

  • 可能出现一次降序,可能出现两次降序。
    • 若出现一次降序,则这两个值就是换位节点;
    • 若出现两次降序,则第一次降序的较大值和第二次降序的较小值为换位节点
  • 可以用非递归方式中序遍历二叉搜索树来实现

打印纸的折痕

题目见 FoldPaper

思路:

  1. 使用一个队列才存结果
  2. 每个 fold 里,先递归调用 fold,再将当前折痕方向入队,再递归调用 fold
  3. 从队列依次取出折痕即可

注意:

  • 每个 fold 里的前后两次调用,方向相反,一上一下,和折纸方向有关

二叉树整棵树上节点间最大距离

题目见 LongestDistance

思路:

  1. 递归的调用 find,每步迭代更新这两个值(当前子树的节点最大距离,到当前子树根结点的最大长度):(MaxLength,MaxToRoot),并将其返回
  2. 当前的 MaxToRoot = max(左子树的 MaxToRoot,右子树的 MaxToRoot) + 1
  3. 当前的 MaxLength = max(一边的最大距离,两边的最大距离)
    • 一边的最大距离 = max(左子树的 MaxLength,右子树的 MaxLength)
    • 两边的最大距离 = 左子树的 MaxToRoot + 右子树的 MaxToRoot + 1

注意:

  • 需要返回两个值,所以用数组当返回类型
  • 分类/划分标准和思路理清了,代码很简单

找到含有节点最多的搜索二叉子树

题目见 MaxSubtree

思路:

  1. 需要记录满足条件搜索二叉树的最大值,最小值,节点个数,记为数组 info[],并返回该搜索二叉树的根节点
  2. 每一步递归对左孩子和右孩子调用,然后分情况讨论
    • 左孩子的调用结果是左孩子,右孩子的的调用结果是右孩子,且左右孩子和根节点满足大小关系,更新上述 info[],返回根节点
    • 不满足上面的条件则从左右调用结果中选择节点个数大的结果(题目要求),更新上述 info[],返回调用结果
    • 左右节点个数相等,选择根结点值大的,更新上述 info[],返回调用结果

注意:

  • 空节点判断,数组初始化(最大值,最小值,个数0)
  • 更新 info[] 时,尤其对情况一,需要判断左右孩子是否为空的情况

按层打印二叉树并换行

题目见 TreePrinter

思路:

  1. 使用队列,先将根节点入队
  2. 使用两个指针 last 和 nlast 分别代表当前行的最后一个节点和下一行的最后一个节点,初始值均为 root
  3. 每次从队列取出一个节点,并将其左右节点入队,每入队一个,更新 nlast 为入队的节点
  4. 判断当前取出的节点是否为 last,若是,则说明这时此行最后一个,故更新 last = nlast

注意:

  • 每出队一个节点,入队其左右孩子,这里 每次 都需要更新 nlast,因为不知道下一行在何时开始没新节点加入
  • 结尾条件需要注意,只有当前节点为 last 且此时队列还非空时,才进行 last 的更新,同时换行,非空这个需要判断,否则会多出一个空行

递归方式实现二叉树的先序、中序和后序的遍历

一定是先左后右,先序、中序和后序指的是根节点遍历的先后

题目见 TreeToSequence

思路:

  1. 递归调用即可,终止条件是该节点为 null
  2. 不为 null,则将二叉树的“左”,“根”,“右”按遍历顺序的要求打印

注意:

  • 没啥注意的,三四行代码就完了

非递归方式实现二叉树的先序、中序和后序的遍历

题目见 TreeToSequence2

都是使用 来实现的

先序遍历

思路:有点像深度优先遍历

  1. 使用一个栈,先将根节点压栈,当栈非空时进行以下步骤
  2. 每次出栈一个节点,并先将其右孩子压栈,再将其左孩子压栈

注意:

  • 利用栈“后进先出”的特性,使得右孩子会在左孩子之后出栈

中序遍历

思路:

  1. 使用栈,先将根节点入栈,当栈非空时进行以下步骤
  2. 当当前节点和其左孩子均不为空时,将其左孩子入栈,当前节点指向左孩子
  3. 当当前节点为空或者左孩子为空时,从栈顶取出一个,并将当前节点指向右孩子(可能为空)。若该取出的节点有右孩子,则将右孩子入栈。

注意:

  • “当前节点左孩子为空则出栈”用于触发左子树到顶的情况
  • “当前节点为空则出栈”用于触发右孩子为空的回退

后序遍历

思路:核心在于使用最近访问节点 last 来标记是从左孩子还是右孩子遍历完返回的,从而确定是入栈还是出栈

  1. 使用栈,先将根节点入栈,当栈非空时进行以下步骤
  2. 每次查看栈顶节点(但不出栈),根据栈顶节点的情况分类判断:
    • 左孩子非空且上次访问既不为左孩子也不为右孩子,则左孩子入栈
    • 否则,若右孩子非空且上次访问不为右孩子,则右孩子入栈
    • 否则,表示此时左右孩子均为空或均访问过,栈顶出栈,并记为最近访问节点 last

注意:

  • 按上面的逻辑左孩子出栈后,右孩子才会入栈,所以是先左后右的顺序
  • 右孩子是上次访问的节点时,前两条都不满足,所以一定会是孩子的根结点出栈

作者@brianway更多文章:个人网站 | CSDN | oschina

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部