104. 二叉树的最大深度

104. 二叉树的最大深度

递归解法

public class Solution {
    public int maxDepth(TreeNode root) {
        return recursion(root, 0);
    }
    // 递归计算树的最大深度
    public int recursion(TreeNode node, int depth) {
        // 递归终止条件：节点为空，说明到底了
        if (node != null) {
            // 分别遍历左子树与右子树
            return Math.max(recursion(node.left, depth + 1), recursion(node.right, depth + 1));
        }
        return depth;
    }
}

迭代解法

public class Solution {
    // 广度优先遍历，该方法类似树的层序遍历，记录树有多少层然后直接返回就行
    public int maxDepth(TreeNode root) {
        // 记录树深度
        int depth = 0;
        // 广度优先使用队列存放节点
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            // 层数 +1
            depth ++;
            // 遍历当前层，将下一层的所有节点放入队列
            for (int i = queue.size(); i > 0; i --) {
                TreeNode tempNode = queue.poll();
                if (tempNode.left != null) queue.add(tempNode.left);
                if (tempNode.right != null) queue.add(tempNode.right);
            }
        }
        return depth;
    }
}