題目鏈接

給定一個(gè)二叉樹，找出其最大深度。

二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

說(shuō)明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例：

給定二叉樹 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解答

public int maxDepth(TreeNode root) {
        // 1.廣度優(yōu)先解法 BFS (層序遍歷解法)
        /*int maxDepth = 0, currLevelNodeCount = 0, nextLevelNodeCount = 0; // currLevelNodeCount:本次深度中節(jié)點(diǎn)個(gè)數(shù)
        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.深度優(yōu)先解法 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));
    }