本文共 1223 字，大约阅读时间需要 4 分钟。

给定二叉树的根节点，计算其最大深度。最大深度是指从根节点到最远叶子节点的路径上的节点数。

示例

方法讨论

计算二叉树最大深度的方法有两种常见的选择：深度优先遍历（DFS） 和 广度优先遍历（BFS）。

深度优先遍历（DFS）

这种方法从根节点开始，尽可能深地遍历每一条路径。当到达叶子节点时，记录当前深度。然后比较左右子树的最大深度，取较大的那个，再加一就是当前节点的深度。

优点：实现简单，直接且高效。缺点：可能会遇到栈溢出问题，如果树的深度很大。

广度优先遍历（BFS）

这种方法按照层序处理节点，每层处理完所有节点之后，记录层数，直到找到最远的叶子节点层。

优点：稳定性好，避免了栈溢出的问题。缺点：可能占用更多内存资源。

代码实现

深度优先遍历（DFS）

public int maxDepth(TreeNode root) {    if (root == null) {        return 0;    }    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}

广度优先遍历（BFS）

import java.util.Queue;import java.util.LinkedList;public int maxDepth(TreeNode root) {    if (root == null) {        return 0;    }    Queue
   
     queue = new LinkedList<>();    queue.offer(root);    int sum = 0;    while (!queue.isEmpty()) {        int size = queue.size();        while (size > 0) {            TreeNode node = queue.poll();            if (node.left != null) {                queue.offer(node.left);            }            if (node.right != null) {                queue.offer(node.right);            }            size--;        }        sum++;    }    return sum;}
   

总结

两种方法都能有效地计算二叉树的最大深度。选择哪种方法取决于具体的应用场景。如果预期树的深度不会过深，DFS实现可能更高效。否则，BFS方法更为稳定。

转载地址：http://sqefk.baihongyu.com/