python求二叉树最大深度

三种方法，作记录用
1递归：在每个节点选择最大的深度+1返回(左子树或右子树的深度)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        
        if (root==None):
            return 0
        num_left = self.maxDepth(root.left) + 1
        num_right = self.maxDepth(root.right) + 1

        if num_left >= num_right:
            return num_left
        
        return num_right

2BFS：使用队列，按层遍历(每次迭代一层)

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if(root==None):
            return 0
        queue = [root]
        count = 0
        while(queue):
            count += 1
            size = len(queue)
            while(size):
                size -= 1
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return count

3DFS：使用双栈，一个存储节点，一个记录该节点所在深度，并记录下遍历过程中的深度最大值

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if(root==None):
            return 0
        stack1 = [root]
        stack2 = [1]
        maxd = 1
        while(stack1):

            node = stack1.pop()
            depth = stack2.pop()
            maxd = max(maxd,depth)

            if node.left:
                stack1.append(node.left)
                stack2.append(depth + 1)
            if node.right:
                stack1.append(node.right)
                stack2.append(depth + 1)
        
        return maxd