LeetCode104-二叉树的最大深度（动态规划，DFS，BF

# 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
        if not root.left and not root.right:
            return 1
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
------------------------------------------------------------------------------------------------
        # 迭代求解树的高度
        if not root:
            return 0
        treeHeight = 0
        queue = [root]
        while queue:
            next_queue = []
            treeHeight = treeHeight + 1
            for node in queue:
                if not node:
                    continue
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            queue = next_queue
        return treeHeight

上面的第一种方法本质上应该是一种动态规划的解法，第二种法中迭代法实际上的BFS的方式求解树高，下面再给出第三种DFS求解树高的方法：

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        self.levelHeight = 0
        self.dfs(root, 1)
        return self.levelHeight
        
    def dfs(self, root, level):
        if not root:
            return 0
        if self.levelHeight < level:
            self.levelHeight += 1
        self.dfs(root.left, level + 1)
        self.dfs(root.right, level + 1)