二叉树的最大深度

一、104. 二叉树的最大深度

自顶向下： 知道某个节点的深度，就知道其子节点的深度。通过递归知道最大深度。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: # 输入空节点
            return 0
        # 递归求取最大深度
        return self.updateDepth(root, 1)
    
    def updateDepth(self, node: TreeNode, depth: int) -> int:
        if not node:
            return depth
        # 叶子节点
        if not node.left and not node.right:
            return depth
        
        # 左子节点或有子节点存在, 递归求取最大深度
        return max(self.updateDepth(node.left, depth+1), self.updateDepth(node.right, depth+1))

“自底向上” 是另一种递归方法。 在每个递归层次上，我们首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。 这个过程可以看作是后序遍历的一种。 通常， “自底向上” 的递归函数

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return self.updateDepth(root)
    # 自底向上： 
    def updateDepth(self, node: TreeNode) -> int:
        if not node:
            return 0
        # 对每个子节点递归调用， 获取其深度，
        leftDepth = self.updateDepth(node.left)
        rightDepth = self.updateDepth(node.right)
        
        # 遇到叶子节点
        return max(leftDepth, rightDepth) + 1
        

二、559. N叉树的最大深度

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        elif root.children == []:
            return 1
        else:
            hs = [self.maxDepth(c) for c in root.children]
            return max(hs) + 1