题解 | #二叉树的最大深度#

DFS

• 遇到树的dfs首先想到的就是递归
• 先到达最左端，在去以同样的方式到达子树的最右端。然后回溯到上一级左端，再遍历上一级左端的右子树
• 由于输入在前，所以在遍历left时，ans+=1在前面
• 而right的输入在后，所以应该等到right的输入出现后，ans+=1，所以ans+=1在right递归的后面
• maxlen存储所有的ans，也可以使用常量变量进行存储

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
#
class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # write code here
        def dfs(root,ans,maxlen):
            if not root:
                maxlen.append(ans)
                return
            ans+=1
            dfs(root.left,ans,maxlen)
            dfs(root.right,ans,maxlen)
            ans+=1
            
        ans,maxlen=0,[]
        dfs(root,ans,maxlen)
        return max(maxlen)