二叉树的最大深度

自底向上

思考方式：对于树中任意一个节点，如果知道它子节点的答案，能够计算出该节点的答案吗？
如果答案是肯定的，那么就可以采用“自底向上”的递归方式。

# 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 root is None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

自顶向下

思考方式：对于树中任意节点，能够从该节点自身出发寻找解决问题的答案吗？
确定该节点的一些参数，应该给子节点传递什么参数。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    max_deep = 0
    def maxDepth(self, root: TreeNode, deep=0) -> int:
        # 自顶向下
        def dfs(node, depth):
            if node is None:
                return depth
            return max(dfs(node.left,depth+1),dfs(node.right,depth+1))
        return dfs(root,0)

ps：也可以层序遍历，计算遍历多少层

class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """ 
        stack = []
        if root is not None:
            stack.append((1, root))
        depth = 0
        while stack != []:
            current_depth, root = stack.pop()
            if root is not None:
                depth = max(depth, current_depth)
                stack.append((current_depth + 1, root.left))
                stack.append((current_depth + 1, root.right))
        return depth