輸入一棵二叉樹(shù)，求該樹(shù)的深度。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過(guò)的結(jié)點(diǎn)（含根、葉結(jié)點(diǎn)）形成樹(shù)的一條路徑，最長(zhǎng)路徑的長(zhǎng)度為樹(shù)的深度。

難度：易
計(jì)算二叉樹(shù)深度的問(wèn)題是基于二叉樹(shù)的廣度優(yōu)先遍歷，以下是遞歸和非遞歸 寫(xiě)法。

遞歸寫(xiě)法

public int TreeDepth(TreeNode root) {
    if(root == null) return 0;// 遞歸出口
    // 樹(shù)的高度 = 左子樹(shù)和右子樹(shù)中高的那個(gè) 加1
    return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}

非遞歸寫(xiě)法 計(jì)數(shù)器法

public int getDeep2(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root); // 添加到隊(duì)列中
    int count = 1, depth = 0; // 初始化當(dāng)層節(jié)點(diǎn)數(shù)，深度計(jì)數(shù)器
    while (queue.size() != 0) {
        TreeNode node = queue.poll();
        count--;// 沒(méi)讀取一個(gè)節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)計(jì)數(shù)器-1
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
        if (count == 0) {// 如果當(dāng)前層讀取完畢
            depth++;// 深度+1
            count = queue.size();// 重置計(jì)數(shù)器大小
        }
   }
   return depth;
}

非遞歸寫(xiě)法 分層標(biāo)志法

class Solution {
    public int maxDepth(TreeNode root) {
        // 廣度遍歷求深度
        // 定義一個(gè)Queue，分層標(biāo)志 null
        // 或者設(shè)置分層標(biāo)志
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int deepth = 0;

        queue.offer(root);
        queue.offer(null);
        
        while(queue.size() != 1){
            TreeNode node = queue.poll();
            if(node != null) {
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }else{
                queue.offer(null);
                deepth++;
            }
        }
        return deepth+1;
    }
}