---

樹

樹是一種非線性的數據結構，它是由n個有限結點組成一個具有層次關系的集合。

樹的相關名詞：

• 根節點：沒有前驅結點的結點。
• 父節點，子節點：有 節點C 為 節點E 的前驅節點（那么 E 就是 C 的后繼節點），稱 C 為 E 的父節點， E 為 C 的子節點。
• 兄弟節點：具有相同的父節點的結點互稱為兄弟節點，如B,C是兄弟節點
• 深度（高度）：從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度。
• 度：該節點的子節點個數。樹的度則是其中節點度的最大值。
• 邊：父子節點間的連線，N 個節點有 N-1 條邊。
• 葉子節點：度為零的結點為葉子節點，如下圖中所有#

二叉樹

二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹。特點如下：

• 每個節點最多有兩棵子樹，即二叉樹不存在度大于2的節點
• 二叉樹的子樹有左右之分，其子樹的次序不能顛倒

滿二叉樹和完全二叉樹

滿二叉樹：

一個二叉樹，如果每一層的節點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且節點總數為(2^k)-1，則就是滿二叉樹

完全二叉樹：

滿二叉樹是一種特殊的完全二叉樹，對于深度為k的，有n個節點的二叉樹，當且僅當每一個節點都與深度為K的滿二叉樹中編號1~n的結點相對應時稱為完全二叉樹

有一個很好的區分它們的方法：滿二叉樹是除葉子節點外所有節點都存在左右子樹的一棵樹，而完全二叉樹則是所有節點都是連續的，不存在有右子樹而沒有左子樹的情況

二叉樹的性質

• 一棵非空二叉樹上的 第n層 最多有 2^n-1 個節點（層數從1開始）
• 深度為n 的二叉樹的最大節點數為 2ⁿ - 1 個
• 如果葉子節點的個數為 n0 ，度為2 的結點的個數為 n2 ，則有 n0 = n2 + 1
• 具有 n 個節點的完全二叉樹的深度為 log2(n) + 1
• 如果 某結點 的編號為 i（從0開始），那么他的 左孩子 編號為 2i +1 ， 右孩子 編號為 2i +2 ，他的 父節點 為 (i - 1) / 2 。

代碼實現求二叉樹的深度

求樹的深度需要遍歷樹的所有節點，樹的遍歷方式總體分為兩類：

深度優先搜索（DFS）、廣度優先搜索（BFS）；

• 常見的 DFS ： 先序遍歷、中序遍歷、后序遍歷；
• 常見的 BFS ： 層序遍歷（即按層遍歷）。

本文將介紹基于 后序遍歷（DFS） 和 層序遍歷（BFS） 的兩種解法。

• DFS深度優先搜索：

/**- 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==nullptr) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

• BFS廣度優先搜索：

class Solution { // 層序遍歷
public:int maxDepth(TreeNode* root) {if(root==nullptr) return 0;queue<TreeNode*> que;que.push(root);int res = 0;while(!que.empty()){queue<TreeNode*> tmp;while(!que.empty()){TreeNode* node = que.front();que.pop();if(node->left) tmp.push(node->left);if(node->right) tmp.push(node->right);}que = tmp;res++;}return res;}
};