JZ55 二叉樹的深度

描述

輸入一棵二叉樹，求該樹的深度。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度，根節(jié)點的深度視為 1 。

成都創(chuàng)新互聯(lián)長期為上千客戶提供的網(wǎng)站建設(shè)服務(wù)，團隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為湞江企業(yè)提供專業(yè)的成都網(wǎng)站建設(shè)、成都做網(wǎng)站，湞江網(wǎng)站改版等技術(shù)服務(wù)。擁有十載豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。

方法1 遞歸

思路：

最大深度是所有葉子節(jié)點的深度的最大值，深度是指樹的根節(jié)點到任一葉子節(jié)點路徑上節(jié)點的數(shù)量，因此從根節(jié)點每次往下一層深度就會加1。因此二叉樹的深度就等于根節(jié)點這個1層加上左子樹和右子樹深度的最大值。而每個子樹我們都可以看成一個根節(jié)點，繼續(xù)用上述方法求的深度，于是我們可以對這個問題劃為子問題，利用遞歸來解決：
  終止條件： 當進入葉子節(jié)點后，再進入子節(jié)點，即為空，沒有深度可言，返回0.
  返回值： 每一級按照上述公式，返回兩邊子樹深度的最大值加上本級的深度，即加1.

代碼

if(root == null) {
          return 0;
      } else {
          return Math.max(TreeDepth(root.left), TreeDepth(root.right)) +1;
      }

方法2 層次遍歷

思路

必須是一層一層的，那一層就是一個深度，有的層可能會很多節(jié)點，有的層如根節(jié)點或者最遠的葉子節(jié)點，只有一個節(jié)點，但是不管多少個節(jié)點，它們都是一層。因此我們可以使用層次遍歷，二叉樹的層次遍歷就是從上到下按層遍歷，每層從左到右，我們只要每層統(tǒng)計層數(shù)即是深度。

代碼

package esay.JZ55二叉樹的深度;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}

public class Solution {
    public int TreeDepth(TreeNode root) {
        //方法1
        /*if(root == null) {
            return 0;
        } else {
            return Math.max(TreeDepth(root.left), TreeDepth(root.right)) +1;
        }*/

        if (root == null) return 0;
        Queue queue = new LinkedList<>();
        queue.add(root);
        int res = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res++;
        }
        return res;
    }
}