90%的二叉树问题都可以用分治来实现

二叉树三种遍历 (前中后是相对于根) (DFS)

  • 前序遍历 (preorder) 根左右
    两种方法,一种是递归写法,一种是非递归写法。
    一般都是考非递归写法(使用栈)
    递归实现:
    1. 遍历写法(traverse),一般情况下,递归的时候不会返回任何的值。因为所有的处理都是处理全局变量(result) 遍历实现思路:top-down
    2. 分治的时候一般情况下都需要返回值(思想:要想知道他的前序遍历是什么,首先要知道他的左子树和右子树的前序遍历是什么) (这个也是要递归的) 分治实现思路:bottom-up
      非递归实现: 用stack记录当前已经走过的root
  • 中序遍历 (Inorder) 左根右
  • 后序遍历 (postorder) 左右根

三种遍历的非递归方式

  • 前序遍历: stack, result两个变量, stack加上root, while stack, 里面 result.append(val), stack 加上右子树,stack加上左子树

递归三要素

如traverse,(把root为根的preorder放到result里面)

  • 对递归要有定义 (就是确定好程序执行结束之后会发生的事情是什么)
  • 递归的拆解 (把大的问题拆成小的问题)
  • 递归的出口

二叉树深度优先遍历搜索

ResultType

  • class ResultType { int var1, var2; }
  • divide要return的东西不是一个东西就可以解决,这个时候用一个ResultType来剞劂
  • 用python或者 swift等可以直接返回一个tuple就行,但是java等就需要用到这样一个类

平衡二叉树

  • 对于每一个二叉树,他的左右子数的高度的差都不超过1(traverse)
  • 对于每个平衡二叉树,他的左,右子树都是平衡二叉树,他的左右子树高度不超过1 (divide-conquer)

##BST Binary Search Tree(二叉搜索树, 二叉查找树)
定义:左子树小于根节点,右子数大于等于根节点
效果:中序遍历(左根右)为”不下降”序列
性质:中序遍历为不下降,但是即使中序遍历为不下降,也不一定是一个二叉搜索树如 左1-1 右1-1。

二叉树通用时间复杂度计算公式

  • O(二叉树的节点个数N * 每个节点的处理时间)

快速排序

先整体有序,再局部有序.不需要使用额外空间

1.数组中随便跳一个数NUM[k],(一般取中间的数),把小于k的放在左部分,大于k的放在右边。
2.quicksort(左边),quicksort(右边)
最坏时间复杂度O(n2), 均摊复杂度O(Nlogn)

mergesort

先局部有序,再整体有序

1.先中间劈一刀,左边部分归并,右边部分归并
2.合并这两个数组.这个时候就需要很大的额外空间
最坏O(Nlogn), 最好O(Nlogn)

快排和mergesort的区别。快排是一个不稳定的排序, 因为里面有swap,mergesort是稳定排序

时间复杂度计算: T(n) = 2 * T(n/2) + O(n) 两个时间n/2的时间复杂度加上merge的时间复杂度
所以时间复杂度是O(Nlogn)