算法（六）二叉树

2018-09-20

本文简单介绍一下二叉树的遍历以及二叉树的相关题目。

1. 二叉树的遍历

1.1 前序遍历

根节点->左子树->右子树

#递归实现
#没有返回值的递归
def traversal(node, result):
    if not node:
        return
    result.add(node.val)
    traversal(node.left, result)
    traversal(node.right, result)

#分治实现
#分而治之，带返回值的递归
def preorderTraversal(node):
    result = []
    if not node:
        return result
    left = preorderTraversal(node.left)
    right = preorderTraversal(node.right)
    result.append(root.val)
    result += left
    result += right
    return result

1.2 中序遍历

左子树->根节点->右子树

# 递归不带返回值
def traversal(node, result):
    if not node:
        return
    traversal(node.left, result)
    result.add(node.val)
    traversal(node.right, result)

# 分治算法
def middleTraversal(node):
    result = []
    if not node:
        return result
    left = middleTraversal(node.left)
    result += left
    result.append(node.val)
    right = middleTraversal(node.right)
    result += right
    return result

1.3 后序遍历

左子树->右子树->根节点

def traversal(node, result):
    if not node:
        return
    traversal(node.left, result)
    traversal(node.right, result)
    result.add(node.val)

1.4 非递归实现二叉搜索数的遍历

非递归就是栈的实现，用栈来模拟递归调用，参考文档https://juejin.cn/post/6844903503807119374

先序遍历
不需要入栈，每次遍历到“左”节点，立即输出即可。

需要注意的是，遍历到最左下的节点时，实际上输出的已经不再是实际的根节点，而是实际的左节点。这符合先序的定义。

def preorderTraversal(node):
    res, stack = [], []
    if not root: return res
    
    cur = root
    while stack or cur:
        while cur:
            res.append(cur.val)
            stack.append(cur)
            cur = cur.left
        top = stack.pop()
        #转向
        cur = top.right

中序遍历
基于对先序的分析，先序与中序的区别只在于对“左”节点的处理上，我们调整一行代码即可完成中序遍历。注意，我们在出栈之后才访问这个节点。因为先序先访问实际根，后访问实际左，而中序恰好相反。相同的是，访问完根+左子树（先序）或左子树+根（中序）后，都需要转向到“右”节点，使“右”节点称为新的“左”节点。

def inorderTraversal(node):
    res, stack = [], []

    if not root: return res

    cur = root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        top = stack.pop()
        res.append(top.val)
        cur = top.left

后序遍历
后序遍历是左右中，按照中右左入栈，然后逆序就可以。

def postorderTraversal(node):
    res, stack = [], []

    if not root: return res

    cur = root
    while stack or cur:
        while cur:
            res.append(cur.val)
            stack.append(cur)
            cur = cur.right
        top = stack.pop()
        cur = top.left
        
    return res[::-1]

方法二：

def postorderTraversal(self, root):
    res, stack = [], []

    if not root: return res

    cur = root
    prev = None

    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        top = stack.pop()
        if not top.right or top.right == prev:
            res.append(top.val)
            prev = top
            cur = None
        else:
            stack.append(top)
            cur = top.right
    
    return res

2.运用递归解决树的问题

递归分为”自底向上”,”自顶向下”的递归

2.1 自顶向下的递归

自顶向下的递归，就是记录经过的path，继续执行下一个step，下面是一个自顶向下求解二叉树深度的例子

def max_depth(node, depth):
    if not node:
        return
    if not node.left and not node.right:
        max_depth = max(max_depth, depth)
    max_depth(node.left, depth +1)
    max_depth(node.right, depth +1)

2.2 自底向上的递归

自底向上是带返回值的递归

def max_depth(node):
    if not node:
        return 0
    left = max_depth(node.left)
    right = max_depth(node.right)
    return max(left, right) +1

3. 二叉树相关题

3.1 最近公共祖先

"""
分治思想
"""
def LCA(root, p1, p2):
    if not root:
        return None
    if root == p1 or root == p2:
        return root
    
    left = LCA(root.left, p1, p2)
    right = LCA(root.right, p1, p2)
    
    #表明p1和p2分别在left和right子树，所以root就是最近公共祖先
    if left and right:
        return root
    #表明p1,p2都在左子树，所以left就是最近公共祖先
    if left:
        return left
    #表明p1,p2都在又子树，所以right就是最近公共祖先
    if right:
        return right

3.2 二叉树root到叶子节点的最大和

def maxPath(root):
    if not root:
        return 0
    
    left = self.maxPath(root.left)
    right = self.maxPath(root.right)
    return max(left, right) + root.val

3.3 二叉树root到任意节点的最大和

def maxPath(root):
    if not root:
        return 0
    
    left = self.maxPath(root.left)
    right = self.maxPath(root.right)
    #如果子树和小于0，还不如不要
    return max(0, left, right) + root.val

3.4 二叉树任意节点到任意节点的最大和

两个分治
首先讨论情况，主要分三种，

垮root节点路径在root的两边
该类问题结果就是 max(root.left to any的最大值, 0) + max(root.right to any 的最大值, 0 )+ root.val
路径全在左子树: 递归调用即可
路径全在由子树: 递归调用即可

def maxPathAny2Any(node):

    #加缓存节省时间
    @lru_cache(None)
    def maxPathRoot2Any(node):
        if not node:
            return 0
        left = maxPathRoot2Any(node.left)
        right = maxPathRoot2Any(node.right)
        return max(left, right, 0) + node.val
    
    # 因为至少有1个节点，所以返回最小值
    if not node:
        return -float("inf")
    
    # 如果小于0,我还不如不要
    left2any = max(maxPathRoot2Any(node.left), 0)
    right2any = max(maxPathRoot2Any(node.right), 0)
    
    # 比较垮root，全在左子树，全在右子树的情况，取最大值
    return max(left2any+right2any+node.val, maxPathAny2Any(node.left), maxPathAny2Any(node.right))