??前面的話??

大家好！本篇文章將介紹的劍指offerOJ題，來自力扣劍指 Offer 55 - I. 二叉樹的深度題解，本文將以這道題為背景介紹有關二叉樹深度的知識，展示代碼語言暫時為：Java，C/C++，

📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
📆首發時間：🌴2021年12月20日🌴
??堅持和努力一定能換來詩與遠方！
💭刷題推薦書籍：📚《劍指offer專項版》，📚《劍指offer第2版》
💬參考在線編程網站：🌐牛客網🌐力扣
博主的碼云gitee，平常博主寫的程式代碼都在里面，
博主的github，平常博主寫的程式代碼都在里面，
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！

??劍指 Offer 55 - I. 二叉樹的深度??

🔐題目詳情

輸入一棵二叉樹的根節點，求該樹的深度，從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度，

例如：

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

    3
   / \
  9  20
    /  \
   15   7

回傳它的最大深度 3 ，

💡解題思路

預備知識：

問題1：什么是樹？

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，

樹： T = { D ， R } T=\{D，R\} T={D，R}， D D D是包含n個結點的有限集合（n≥0），當n=0時為空樹，否則關系R滿足以下條件:
有且僅有一個結點 d 0 ∈ D d_0∈D d0?∈D，它對于關系R來說沒有前驅結點，結點 d 0 d_0 d0?稱作樹的根結點，
除根結點外，每個結點有且僅有一個前驅結點，
D D D中每個結點可以有零個或多個后繼結點，

• 節點的度：一個節點含有的子樹的個數稱為該節點的度； 如上圖：A的為6，
• 葉節點或終端節點：度為0的節點稱為葉節點； 如上圖：B、C、H、I…等節點為葉節點，
• 非終端節點或分支節點：度不為0的節點； 如上圖：D、E、F、G…等節點為分支節點，
• 雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點； 如上圖：A是B的父節點，
• 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點； 如上圖：B是A的孩子節點，
• 兄弟節點：具有相同父節點的節點互稱為兄弟節點； 如上圖：B、C是兄弟節點，
• 樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6，
• 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推，
• 樹的高度或深度：樹中節點的最大層次； 如上圖：樹的高度為4，
• 有序樹和無序樹：若樹中各結點的子樹是按照一定的次序從左向右安排的，且相對次序是不能隨意變換的，則稱為有序樹，否則稱為無序樹，
• 堂兄弟節點：雙親在同一層的節點互為堂兄弟；如上圖：H、I互為兄弟節點，
• 節點的祖先：從根到該節點所經分支上的所有節點；如上圖：A是所有節點的祖先，
• 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫，

樹結構相對線性表就比較復雜了，要存盤表示起來就比較麻煩了，既然保存值域，也要保存結點和結點之間的關系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等，我們這里就簡單的了解其中最常用的孩子兄弟表示法，
子樹的左結點表示孩子，右節點表示兄弟，簡稱“左孩子右兄弟”，

public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}

問題2：:什么是二叉樹？
一棵二叉樹是結點的一個有限集合，該集合:

1. 為空樹，
2. 由一個根節點加上兩棵別稱為左子樹和右子樹的子二叉樹組成，
3. 二叉樹結點的度不超過2，

二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹，

對于任意的二叉樹都是由以下幾種情況復合而成的：

特殊的二叉樹：

• 1. 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值2，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為 k k k，且結點總數是 2 k ? 1 2^k-1 2k?1，則它就是滿二叉樹，
• 2. 完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為 k k k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為 k k k的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 要注意的是滿二叉樹是一種特殊的完全二叉樹，或者說結點的度為2，最下面一層的葉結點都依次排列在該層最左邊的位置上，即完全二叉樹，

滿二叉樹：

完全二叉樹：

完全二叉樹實際上是對應的滿二叉樹洗掉葉結點層最右邊若干個結點得到的，
問題3：什么是二叉樹的深度？
結點的層次和樹的高度：樹中的每個結點都處在一個層次上，結點的層次從樹根開始定義，根結點為第1層，它的孩子結點為第2層，以此類推，一個結點所在的層次為其雙親結點所在的層次加1，

樹中結點的最大層次稱為樹的高度（或樹的深度），

具有n個結點的m次樹的最小高度為 l o g m ( n ( m ? 1 ) + 1 ) log_m(n(m-1)+1) logm?(n(m?1)+1)，

解題思路：
知道樹的概念和二叉樹深度概念就可以開始做題了，這道題我們可以采取遞回，分別求左子樹與右子樹的深度，取兩者最大值再加上根節點層次就是當前二叉樹的最深深度（最高高度），

遞回條件：
二 叉 樹 結 點 不 為 n u l l ， 為 空 返 回 0 二叉樹結點不為null，為慷訓傳0 二叉樹結點不為null，為空返回0
遞回公式：不妨設左子樹深度為 h i g h L e f t highLeft highLeft，右子樹深度為 h i g h R i g h t highRight highRight，則二叉樹最深深度為 H i g h High High：
H i g h = m a x ( h i g h L e f t ， h i g h R i g h t ) + 1 High=max(highLeft， highRight)+1 High=max(highLeft，highRight)+1

🔑源代碼

Java：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

C:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b)
{
    return a > b ? a : b;
}

int maxDepth(struct TreeNode* root){
    if(root == NULL) 
    {
        return 0;
    }
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) 
        {
            return 0;
        }
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

🌱總結

采取遞回，分別求左子樹與右子樹的深度，取兩者最大值再加上根節點層次就是當前二叉樹的最深深度（最高高度），
類似題如下：
二叉樹的最大深度