极客算法

二叉树与分治算法


二叉树

问题1,如果一颗二叉树🌲,有N个节点,那么它的高度用Big O表示是多少呢?

答案是O(N),因为链表也是一颗独特的二叉树

1 -> 2 -> 3 -> 4 -> 5

二叉树的三种遍历

对于二叉树遍历,它的深度优先搜索DFS,有三种遍历策略,是以遍历root的三种策略命名的

  1. 前序遍历(左右)
  2. 中序遍历(左右)
  3. 后续遍历(左右)

具体遍历,参考之前的文章《树的三种DFS策略(前序、中序、后序)遍历》

递归思想

能否使用递归实现,有一个非常重要的判断标准,就是递归的深度。

现代Linux操作系统,stack大小也只有8M,可以通过ulimit -a查看

不论内存有多大,对于程序来说,有个很小的递归上线,深度大概10K左右。

python更小,只有1K层,左右。有兴趣可以文末链接

递归的三要素

  1. 递归的定义
  2. 递归的拆解
  3. 递归的出口

递归的技巧

对于不能返回多个值的语言,可以定一个类,封装多个值返回

时间复杂度分析

通过O(N)的时间,把N的问题变成N/2的问题, 典型的是归并排序

  T(N) = O(N) + 2 * T(N/2)

       = O(N) + 2 * (O(N/2) + 2 * T(N/4)) = O(N) + O(N) + 4 * T(N / 4) 

       = O(N) + O(N) + 4 * (O(N/4) + 2 * T(N/8)) = O(N) + O(N) + O(N) + 8 * T(N/8)

       ...

       = O(N) + O(N) + O(N) ... + N * (N/ N) = O(N) + O(N) + O(N) + ... + N * O(1)

       = O(N * logN) + O(N)

       = O(N * logN)

通过O(1)的时间,把N的问题变成N/2的问题, 典型是二叉树上的分治算法

  T(N) = O(1) + 2 * T(N/2)

       = O(1) + 2 * (O(1) + 2 * T(N/4)) = O(1) + 2 * O(1) + 4 * T(N / 4) 

       = O(1) + 2 * (N) + 4 * (O(1) + 2 * T(N/8)) = O(1) + 2 * O(1) + 4 * O(1) + 8 * T(N/8)

       ...

       = O(1) + 2 * O(1) + 4 * O(1) ... + N * (N/ N) = (2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ (logN - 1)) * O(1) + N * O(1)

       = (1 + 2 + 4 + ... + N) * O(1) + N * O(1)

       = (2N - 1) * O(1) + N * O(1) = O(3N - 1)

       = O(N)

递归的两种方式

问题:给出一棵二叉树,返回其节点值的前序遍历

分治算法(Divide and Conquer)

特点:

  1. 结果 = 当前值 + 左子树返回值 + 右子树返回值
  2. Bottom-up
def preorderTraversal(self, root):
    return self.traverse(root)
    
def traverse(self, root): # 递归的定义
    if root is None:
        return [] # 递归的出口
      
    results = [] 

    # 递归的拆解-Start
    lefts = self.traverse(root.left)
    rights = self.traverse(root.right)
    
    results.append(root.val)
    results.extend(lefts)
    results.extend(rights)
    
    return results
    # 递归的拆解-End

遍历算法(Traverse)

特点:

  1. 结果 = 一个全局变量results,从根一层层搜集结果
  2. Top-down
def preorderTraversal(self, root):
    results = []
    self.traverse(root, results)
    return results
    
def traverse(self, root, results): # 递归的定义
    if root is None:
        return # 递归的出口

    # 递归的拆解-Start
    results.append(root.val)
    self.traverse(root.left, results)
    self.traverse(root.right, results)
    # 递归的拆解-End

二叉搜索树BST

问题2, 如果一颗二叉搜索树🌲(BST), 有N个节点,那么它的高度用Big O表示是多少呢?

没有提到平衡,BST的高度也有可能是O(N), 例如下图高度=N/2

常用的平衡二叉树有红黑树

      4
    3   5
  2       6
1           7

二叉搜索树BST特点

  1. 左子树都小于root的值(不推荐把等于放在这里)
  2. 右子树都大于root的值(也可以等于)

BST必要不充分特点

对于BST,进行中序遍历,结果是一个不下降序列

参考:

《程序语言递归深度》 https://rosettacode.org/wiki/Find_limit_of_recursion

–End–


相关推荐

评论

内容: