104.二叉树的最大深度(二叉树，简单)

题目链接

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解答

public int maxDepth(TreeNode root) {
        // 1.广度优先解法 BFS (层序遍历解法)
        /*int maxDepth = 0, currLevelNodeCount = 0, nextLevelNodeCount = 0; // currLevelNodeCount:本次深度中节点个数
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        currLevelNodeCount++;
        TreeNode node;
        boolean flag = false;   // 记录本层是否已更新二叉树深度
        while (!nodeQueue.isEmpty()) {
            node = nodeQueue.poll();
            if (currLevelNodeCount <= 0) {
                currLevelNodeCount = nextLevelNodeCount;
                nextLevelNodeCount = 0;
                flag = false;
            }
            currLevelNodeCount--;
            if (node != null) {
                if (!flag) {
                    flag = true;
                    maxDepth++;
                }
                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                nextLevelNodeCount += 2;
            }
        }
        return maxDepth;*/
        // 2.深度优先解法 DFS (递归解法)
        return getMaxDepth(root);
    }

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