BinaryTree二叉树整理

前言

上一篇博客中,我们和大家简单的了解了一下BST二叉搜索树,但是实际上,这个可能工程实际中用的多,在实际面试的时候,可能更加关注的是二叉树这种更一般的情况。本着不懂就问,不会就学的态度,周末在家稍微整理了一些碎片化的知识,希望在这篇博客中能够把它们串联起来。

作为一个nlp算法工程师,我觉得tree+图是必不可少的技能,甚至你可以不了解word embedded,但是这两个技能真的是需要去好好学习一下的。实际项目中,我遇到了一个问题,快速查找6级地址,并进行联想,如果用传统的kv的hashmap查找,这个真的是一个redis灾难性的问题,但是基于树的Tire树就可以很好的解决这个问题。这也是促使我去学习更新自己技能的原因,话不多说,让我们开始:

思考

二叉树的思考策略:

  • 递归
    • 万能,基本上树的问题都可以用递归去执行,天生的结构形式决定
  • 迭代
    • 队列:层次遍历
    • 栈:三种迭代递归
    • dp:需要结合动态规划的

实际去用的过程中,建议优先考虑递归,相对来说更加简单,而迭代的边界考虑更为复杂。

基本递归

  • 先序遍历preOrderTraverse
  • 中序遍历inOrderTraverse
  • 后序遍历posOrderTraverse
    三种遍历问题和BST三种遍历方式一致,代码在这边。最简单,也是最基础的,后面很多题型回基于这个问题去做,务必掌握。
  • 层序遍历levelOrderTraverse
    两种方式去实现层序遍历
  • 把二叉搜索树转换为累加树
    改写遍历方式的问题:

    1
    2
    3
    4
    5
    1、先遍历到右树的根树,然后把根树的value赋值给add
    2、更新此树对应的父结点,并更新父结点对应的value = value+add
    3、同时再更新add,把父结点的值也更新到add上
    4、再更新父结点的左子树的value结点
    5、这样一次更新便完成了
  • 验证二叉搜索树
    搜索二叉树的左支<结点<右支,正好可以用中序遍历比较

    BST两个特点
    1、左支<结点<右支
    2、无重复

  • 判断两个树是否一致(待完成,leetcode100)
  • 对称二叉树
    以上两题利用了层次遍历的技巧

简单升级递归

以上的递归围绕着简单遍历,实际上有更多剑走偏锋的问题:

  • 二叉树最大深度
  • 二叉树最小深度(待完成,leetcode111)
  • 合并二叉树
  • 翻转二叉树
    这四题都是直接利用递归结果之间的各种条件下的判断结果进行传递,没有额外的变量参与。典型的形式就是:
    1
    2
    def func():
    return new_func(func(root.left),func(root.right))

技巧递归

  • 二叉树所有路径和(待完成,leetcode257)
  • 二叉树中的最大路径和
    • 借助了当前结点是否可以作为根结点通过,利用全局变量保存每一个结点的路径最大值
    • 借助了当前结点作为下一次迭代结点的时候,进行选左支还是右支考虑
  • 二叉树的直径
    遍历所有结点,保存所有结点作为根结点的情况下,左右子树的最大深度和即可

动态规划

  • 不同的二叉搜索树
    状态转移方程为:dp[i] += dp[j - 1] * dp[i - j],总树数=左右子树的分别数量的笛卡尔积

公共祖先问题

恢复原树

  • 从前序与中序遍历序列构造二叉树
  • 从中序与后序遍历序列构造二叉树
  • 从前序与后序遍历序列构造二叉树
    都是先找根节点,再把左右树范围找出来,分别在对左右树范围分别找出根节点,进行循环递归

其他问题

  • 序列化与反序列化
    二叉树-->list//list-->二叉树
    先通过某种遍历方法去把二叉树—>list,再通过data.pop不断的拿结点去赋值,if判断条件用来当数据到最底层时候,跳出此次递归分支,切换到另一个子树上(此处为右子树)
  • dfs+两数之和+双递归
    1
    2
    3
    4
    这题leetcode认为是简单,但是我觉得贼难: 
    1、python闭包的理解,count虽然是局部遍历,但是在递归的时候,每个count都是独立的
    2、dfs(root.?????, sum - root.val)用的是两数之和的逻辑进行递归
    3、dfs(root,sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum) 这个用的是遍历所有结点的方法

以上就是常见问题的整理了,当然必然有一些新的问题,比如二叉树中的第k小的元素(待完成,leetcode230),二叉树的锯齿形层次遍历(待完成,leetcode103),二叉树展开为链表(待完成,leetcode114)等等。但是只要把以上的这么多类别的问题都能搞定,这些问题也只是上述问题的一些翻版而已。

BinaryTree整理就给大家整理到这,如果大家想看更多的数据结构问题,可以关注一下我的Github,希望有所帮助。

欢迎大家关注我的个人bolg知乎,更多代码内容欢迎follow我的个人Github,如果有任何算法、代码、转行疑问都欢迎通过邮箱发消息给我。

打赏的大佬可以联系我,赠送超赞的算法资料