LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )

3
   / \
  9  20
    /  \
   15   7

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

3            <-- Level 1
 / \
9  20          <-- Level 2
  /  \
 15   7        <-- Level 3
调用栈情况（以节点3为例）:
maxDepth(3)
=> maxDepth(9), maxDepth(20)
   => maxDepth(null), maxDepth(null), maxDepth(15), maxDepth(7)

def maxDepthIterative(root):
    if not root:
        return 0
    stack = [(root, 1)]
    max_depth = 0
    while stack:
        node, depth = stack.pop()
        if node:
            max_depth = max(max_depth, depth)
            stack.append((node.left, depth + 1))
            stack.append((node.right, depth + 1))
    return max_depth

栈的操作示例:
初始: [(3, 1)]
操作: 弹出(3, 1), 压入(9, 2), 压入(20, 2)
接着: 弹出(20, 2), 压入(15, 3), 压入(7, 3)
接着: 弹出(7, 3), 弹出(15, 3), 弹出(9, 2)

from collections import deque
def maxDepthUsingBFS(root):
    if not root:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

队列操作示例:
初始: [3]
操作: 弹出3, 压入9, 压入20
接着: 弹出9, 弹出20, 压入15, 压入7
接着: 弹出15, 弹出7

def maxDepthTailRecursive(root, depth=0):
    if not root:
        return depth
    return max(maxDepthTailRecursive(root.left, depth + 1), maxDepthTailRecursive(root.right, depth + 1))

递归调用栈（尾递归）：
maxDepthTailRecursive(3, 0)
=> maxDepthTailRecursive(9, 1), maxDepthTailRecursive(20, 1)
   => maxDepthTailRecursive(null, 2), ...

def maxDepthDivideAndConquer(root):
    if not root:
        return 0
    left_depth = maxDepthDivideAndConquer(root.left)
    right_depth = maxDepthDivideAndConquer(root.right)
    return 1 + max(left_depth, right_depth)

分治递归过程：
maxDepthDivideAndConquer(3)
=> maxDepthDivideAndConquer(9), maxDepthDivideAndConquer(20)
   => maxDepthDivideAndConquer(null), maxDepthDivideAndConquer(null), ...