京公网安备11010502063487号给定一棵二叉树，求从根结点到最远叶子结点的最长路径上的结点数（也就是树的高度）。标准递归写法很简单：1 + max(左子树深度, 右子树深度)。但如果改用栈做迭代 DFS，一个常见陷阱是把"访问过的结点总数"当成"树的高度"——每弹出一个结点就把计数加一。对链状的树这恰好蒙对，但对结点多、树矮的"宽"树会差出好几倍。本文用一组不断增大的完全二叉树验证这个规律，给出正确写法、5 种语言实现，以及递归展开与回溯的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一棵二叉树，返回它的最大深度：从根结点到最远叶子结点的最长路径上的结点数。一共 5 组用例，覆盖：官方示例、空树、单结点、只有右孩子的链、完全二叉树：
[3,9,20,null,null,15,7] → 3 [] → 0 [1] → 1 [1,null,2] → 2 [1,2,3,4,5,6,7] → 3
标准递归写法是 1 + max(左子树深度, 右子树深度)，非常直接。但如果改用迭代、拿一个栈做 DFS，一个容易踩的坑是：把"深度"和"访问过的结点数量"搞混——每从栈里弹出一个结点就把 depth 加 1，这样数的其实是总共访问了多少个结点，而不是树到底有多高。在结点很多但树很矮（很"宽"）的情况下，这两个数字会差得很远：
输入 [1,2,3,4,5,6,7]（7 个结点的完全二叉树，真正的高度是 3）\n正确写法（递归求高度） → 3\n陷阱写法（每弹出一个结点 +1） → 7
用一组不断增大的完全二叉树验证这个规律：
完全二叉树规模 n 与两种写法的输出：\nn= 1 正确高度=1 陷阱输出(结点数)= 1\nn= 3 正确高度=2 陷阱输出(结点数)= 3\nn= 7 正确高度=3 陷阱输出(结点数)= 7\nn= 15 正确高度=4 陷阱输出(结点数)= 15\nn= 31 正确高度=5 陷阱输出(结点数)= 31\nn= 63 正确高度=6 陷阱输出(结点数)= 63\nn=127 正确高度=7 陷阱输出(结点数)=127
陷阱写法输出的数字始终等于树的结点总数 n，而正确高度只是 log₂(n+1)，两者的差距随着 n 增大而线性拉开。对于链状的树（每个结点只有一个孩子），结点数恰好等于高度，这种情况下两种写法碰巧给出一样的结果，容易让人误以为写法是对的——直到遇到一棵比较"宽"的树才会暴露问题。
maxDepth(root)：空树深度是 0；否则是 1 + max(左子树深度, 右子树深度)，左右子树的深度各自也用同样的方式递归求出。时间 O(n)，空间是递归深度 O(h)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def max_depth(root): if root is None: return 0 return 1 + max(max_depth(root.left), max_depth(root.right))
$ python3 solution.py [3,9,20,null,null,15,7] → 3 [] → 0 [1] → 1 [1,null,2] → 2 [1,2,3,4,5,6,7] → 3
Java · 解法代码class Solution { public int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } }
$ javac -d build Main.java && java -cp build Main [3,9,20,null,null,15,7] → 3 [] → 0 [1] → 1 [1,null,2] → 2 [1,2,3,4,5,6,7] → 3
Go · 解法代码func maxDepth(root *TreeNode) int { if root == nil { return 0 } l, r := maxDepth(root.Left), maxDepth(root.Right) if l > r { return l + 1 } return r + 1 }
$ go run solution.go [3,9,20,null,null,15,7] → 3 [] → 0 [1] → 1 [1,null,2] → 2 [1,2,3,4,5,6,7] → 3
JavaScript · 解法代码function maxDepth(root) { if (root === null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }
$ node run.js [3,9,20,null,null,15,7] → 3 [] → 0 [1] → 1 [1,null,2] → 2 [1,2,3,4,5,6,7] → 3
C++ · 解法代码class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin [3,9,20,null,null,15,7] → 3 [] → 0 [1] → 1 [1,null,2] → 2 [1,2,3,4,5,6,7] → 3
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本的递归实现另外和一个独立写的 BFS 版本做了随机对拍：BFS 版用队列按层扩展，每完整处理完一层就把深度计数加 1，处理到队列为空为止。
随机对拍 30,000 组（结点数 0 到 12 的随机二叉树，值取 0/1），递归版与 BFS 版的结果全部一致，0 处不一致。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 [3,9,20,null,null,15,7]：递归从根结点展开，先算左子树的深度，再算右子树的深度，最后取较大值加一回溯给父结点。蓝色是正在展开、还没得到结果的结点，绿色是已经求出深度、正在往上回溯的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。