每日一题：二叉树的最大深度

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

 //两种思想 
 //思想一：遍历 一般没有返回值 就想成遍历二叉树解决问题
 //思想二：分解问题 分解子问题 比如斐波那契数列 
//  
//        ⎧ 0,  n=0
//fib(n)= ⎨ 1,  n=1
//        ⎩ fib(n−1)+fib(n−2), n>1
//思想一
// func maxDepth(root *TreeNode) int {
//     var ans int
//     var dfs func(node *TreeNode,deepth int)
//     dfs = func(node *TreeNode, deepth int){
//         if node == nil{
//             return
//         }
//         //前序遍历（进入节点）增加深度
//         deepth ++
//         if node.Left == nil && node.Right == nil{
//             ans = max(ans,deepth)
//         }
//         dfs(node.Left,deepth)
//         dfs(node.Right,deepth)
//         //后续遍历（离开节点）减少深度
//         //deepth --
//     }
//     dfs(root,0)
//     return ans
// }

//思想二 我们想知道当前节点的最大深度 只需要知道左子树的最大深度和右子树的最大深度取max + 1就好了
func maxDepth(root *TreeNode) int{
    if root == nil{
        return 0
    }
    return max(maxDepth(root.Left),maxDepth(root.Right)) + 1
}

用这棵只有两个节点的树：

    1
   /
  2

func maxDepth(root *TreeNode) (ans int) {
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }
        depth++                  // ① 进来先加1
        ans = max(ans, depth)    // ② 更新最大深度
        dfs(node.Left, depth)    // ③ 去左孩子
        dfs(node.Right, depth)   // ④ 去右孩子
    }
    dfs(root, 0) // 从根节点开始，初始传 0
    return
}

咱们一层一层「进房间、出房间」地走

【第 1 个房间：处理节点 1，传入 depth=0】

• 刚进门，手里拿到的 depth 纸条写着 0
• node 不是空，继续往下走
• 执行 depth++ → 自己的纸条改成 1
• 更新 ans：max(0, 1) = 1，现在 ans=1
• 接下来要去左孩子：dfs(node.Left, 1)→ 把自己手里的 1 抄一张，带给下一个房间👉 现在进入第 2 个房间

【第 2 个房间：处理节点 2，传入 depth=1】

• 刚进门，手里拿到的 depth 纸条写着 1（是上一层抄过来的复印件）
• node 不是空，继续
• 执行 depth++ → 自己的纸条改成 2
• 更新 ans：max(1, 2) = 2，现在 ans=2
• 先去左孩子：dfs(nil, 2)→ 进入一个空房间，node==nil，直接 return，立刻回到第 2 个房间✅ 回来之后，第 2 个房间的 depth 还是 2，根本没变
• 再去右孩子：dfs(nil, 2)→ 又是空房间，直接 return，回到第 2 个房间
• 第 2 个房间的事都做完了，return，回到第 1 个房间

【回到第 1 个房间】

✅ 重点来了：从第 2 个房间回来之后，第 1 个房间里的 depth 还是 1！因为第 2 个房间改的是自己的复印件，没碰第 1 个房间的原件。

• 继续往下走：去右孩子 dfs(nil, 1)→ 空房间，直接 return，回到第 1 个房间
• 第 1 个房间的事都做完了，return，整个递归结束

最终 ans = 2，完全正确。

本作品采用《CC 协议》，转载必须注明作者和本文链接