image

題目

給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
題目地址

解題思路

迭代解法

我們先找子問題，一棵樹的最大深度就是它左子樹和右子樹最大的深度的最大值。

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

那么怎么確認返回值呢，怎么返回左右子樹的深度，我們可以想到每一層迭代都是向下的一層，我們只要每一次迭代都加1就可以了。得到了最終的代碼。

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

迭代解法

關(guān)于迭代的解法，我們只要一層一層的遍歷，遍歷的過程中，記錄層數(shù)即可。思路比較簡單。代碼如下

public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int preCount = 1;
        int pCount = 0;

        int level = 0;

        while (!q.isEmpty()) {
            TreeNode temp = q.poll();
            preCount--;

            if (temp.left != null) {
                q.offer(temp.left);
                pCount++;
            }
            if (temp.right != null) {
                q.offer(temp.right);
                pCount++;
            }

            if (preCount == 0) {
                preCount = pCount;
                pCount = 0;
                // System.out.println();
                level++;
            }
        }
        return level;
    }