二叉树笔记（深度遍历与广度遍历+13道leetcode题目(深度3道、广度10道)）
本文章為結(jié)合leetcode題目以及公眾號“代碼隨想錄”的文章所做的筆記！
感覺代碼隨想錄的題目整理真的很好，比自己盲目刷題好很多。
目錄
- 1、二叉樹小記
- 1、滿二叉樹與完全二叉樹
- 2、二叉搜索樹
- 3、平衡二叉搜索樹AVL
- 4、二叉樹存儲方式
- 5、二叉樹遍歷方式
- 6、二叉樹的定義
- 2、二叉樹深度優(yōu)先遍歷遞歸算法書寫
- 1、leetcode144題：
- 2、leetcode145題：
- 3、leetcode94題：
- 3、二叉樹深度優(yōu)先遍歷迭代算法書寫
- 1、先序遍歷（迭代法）
- 2、中序遍歷（迭代法）
- 3、后序遍歷（迭代法）
- 4、二叉樹深度優(yōu)先遍歷迭代算法格式統(tǒng)一
- 5、二叉樹層序遍歷
- 1、leetcode102:二叉樹的層序遍歷
- 2、leetcode107:二叉樹的層序遍歷 II
- 3、leetcode199:二叉樹的右視圖
- 4、leetcode637:二叉樹的層平均值
- 5、leetcode429:N叉樹的層序遍歷
- 6、leetcode515. 在每個樹行中找最大值
- 7、leetcode116. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針
- 8、leetcode117. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針 II（遇上一題思路代碼一致）
- 9、104. 二叉樹的最大深度
- 10、111. 二叉樹的最大深度
1、二叉樹小記
1、滿二叉樹與完全二叉樹
滿二叉樹：深度為k，有2的k-1個節(jié)點的二叉樹。
完全二叉樹：除了最底層節(jié)點可能沒填滿外，其余每層節(jié)點數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置。若最底層為第h層，則該層包含1~2h個節(jié)點。
2、二叉搜索樹
二叉搜索樹是有數(shù)值的，是一個有序樹。
它的特點：
1、若它的左子樹不空，則左子樹所有結(jié)點的值均小于它根結(jié)點的值
2、若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值
3、它的左右子樹也分別為二叉排序樹
3、平衡二叉搜索樹AVL
AVL是一棵空數(shù)或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
C++中map、set、multimap、multiset的底層實現(xiàn)都是平衡二叉搜索樹，所以map、set的增刪操作時間復(fù)雜度都是logn。
而unordered_map、unordered_set、unordered_map、unordered_map底層實現(xiàn)是哈希表。
4、二叉樹存儲方式
鏈表存儲與數(shù)組存儲。
數(shù)組存儲二叉樹遍歷：如果父節(jié)點的數(shù)組下標(biāo)是i，那么它的左孩子就是i2+1,右孩子就是i2+2.
5、二叉樹遍歷方式
有兩種遍歷方式：
1、深度優(yōu)先遍歷：先往深走，遇到葉子結(jié)點再往回走
分為：前序遍歷、中序遍歷、后序遍歷
這里的前中后，指的是中間結(jié)點的遍歷順序
前序遍歷：中、左、右
中序遍歷：左、中、右
后序遍歷：左、右、中
深度優(yōu)先遍歷使用遞歸是比較方便的，可以借助棧使用非遞歸方式實現(xiàn)。
2、廣度優(yōu)先遍歷：一層一層的去遍歷
分為：層次遍歷
廣度優(yōu)先遍歷一般使用隊列實現(xiàn)，利用了隊列的先進(jìn)先出的特點。這樣才能一層一層的來遍歷二叉樹。
6、二叉樹的定義
二叉樹的定義和鏈表差不多，多了一個指針
struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x),left(NULL),right(NULL) {} };2、二叉樹深度優(yōu)先遍歷遞歸算法書寫
遞歸算法的三個要素：
1、確定遞歸函數(shù)的參數(shù)和返回值
若是在遞歸過程中需要處理某個參數(shù)，就在遞歸函數(shù)里面加上這個參數(shù)。
明確每次遞歸地返回值是什么，進(jìn)而確定遞歸函數(shù)的返回類型
2、確定終止條件
1、如果在遞歸算法運(yùn)行過程中出現(xiàn)棧溢出，大概率是終止條件寫的不對
2、操作系統(tǒng)也是用一個棧的結(jié)構(gòu)來保存每一層遞歸地信息，如果遞歸沒有終止，操作系統(tǒng)的內(nèi)存棧必然就會溢出
3、確定單層遞歸邏輯
確定每一層遞歸需要處理的信息。在這里也會重復(fù)調(diào)用自己來實現(xiàn)遞歸地過程
以前序遍歷為例：
1、因為要打印出前序遍歷結(jié)點的數(shù)值，所以參數(shù)里需要傳入vector放在結(jié)點里的數(shù)據(jù)。沒有返回值
2、在遞歸過程中，如何算是遞歸結(jié)束？如果當(dāng)前遍歷的結(jié)點是空的，那么本層遞歸就結(jié)束了
if(cur == NULL) return;3、前序遍歷是中左右的循序，所以在單層遞歸中就要先取出中結(jié)點的數(shù)據(jù)
vec.push_back(cur->val); //中 traversal(cur->left,vec); //左 traversal(cur->right,vec); //右完整代碼:
class Solution{public:void traversal(TreeNode* cur , vector<int>& vec){if(cur == NULL) return;vec.push_back(cur->val);traversal(cur->left,vec);traversal(cur->right,vec);}vector<int> preorderTraversal(TreeNode* root){vector<int> result;traversal(root,result);return result;} };中序遍歷：
void traversal(TreeNode* cur , vector<int>& vec) {if(cur == NULL) return;traversal(cur->left,vec);vec.push_back(cur->val);traversal(cur->right,vec); }后序遍歷：
void traversal(TreeNode* cur , vector<int>& vec) {if(cur == NULL) return;traversal(cur->left,vec);traversal(cur->right,vec);vec.push_back(cur->val); }1、leetcode144題：
給定一個二叉樹，返回它的 前序 遍歷。
示例:
輸入: [1,null,2,3]
1
2
/
3
輸出: [1,2,3]
2、leetcode145題：
給定一個二叉樹，返回它的 后序 遍歷。
示例:
輸入: [1,null,2,3]
1
2
/
3
輸出: [3,2,1]
3、leetcode94題：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:void traversal(TreeNode* cur , vector<int>& vec){if(cur == NULL) return;traversal(cur->left,vec);vec.push_back(cur->val);traversal(cur->right,vec);}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;} };3、二叉樹深度優(yōu)先遍歷迭代算法書寫
原理：為什么可以使用迭代法(非遞歸地方式)來實現(xiàn)二叉樹的前后中序遍歷？
遞歸地實現(xiàn)就是：每一次遞歸調(diào)用都會把函數(shù)的局部變量、參數(shù)值和返回地址等壓入調(diào)用棧中，
然后遞歸返回的時候，從棧頂彈出上一次遞歸的各項參數(shù)，所以這就是遞歸為什么可以返回上一層位置的原因。
1、先序遍歷（迭代法）
前序遍歷：中左右；每次處理的是中間結(jié)點，先將根結(jié)點放入棧中，然后將右孩子放入棧中，再加入左孩子。
為什么要先加入有孩子，再加入左孩子？
這樣出棧的時候才是中左右的順序。
順序如下：
2、中序遍歷（迭代法）
注意，前序遍歷的迭代法思路不能直接套用到中序遍歷上。
在迭代的過程中有兩個操作:
1、【處理】將元素放入result數(shù)組
2、【訪問】遍歷結(jié)點
前序遍歷中：遍歷的順序是中左右。
先訪問中間結(jié)點，先處理中間結(jié)點
要訪問的元素和要處理的元素的順序一致，都是中間結(jié)點。
而中序遍歷，遍歷順序為左中右。
先訪問二叉樹頂部結(jié)點，然后一層一層向下訪問，直到到達(dá)樹左面的最底部，再開始處理結(jié)點（再把結(jié)點的數(shù)值放到result數(shù)組中）；
這就導(dǎo)致了處理順序和訪問順序不一致
所以在使用迭代 法時，需要借用指針的遍歷來幫助訪問結(jié)點，使用棧來處理結(jié)點上的元素。
3、后序遍歷（迭代法）
后序遍歷：左右中。
先序遍歷：中左右。
我們只需要調(diào)整一下先序遍歷的代碼順序，變?yōu)橹杏易蟮谋闅v順序。
然后反轉(zhuǎn)result數(shù)組，輸出結(jié)果就是左右中。
4、二叉樹深度優(yōu)先遍歷迭代算法格式統(tǒng)一
之前迭代法例子中提到無法同時解決訪問節(jié)點（遍歷）和處理結(jié)點（將結(jié)點放入結(jié)果）不一致的情況。
解決方法：
將訪問的結(jié)點放入棧中，把要處理的結(jié)點也放入棧中，但是要做標(biāo)記
標(biāo)記方法：將要處理的結(jié)點放入棧中之后，緊接著放入一個空指針作為標(biāo)記
將訪問的結(jié)點直接加入到棧中，但是如果是處理的結(jié)點則后面放入一個空結(jié)點，這樣只有空結(jié)點彈出的時候才將下一個結(jié)點放進(jìn)結(jié)果集。
如何知道該訪問的結(jié)點是我們需要處理的結(jié)點？（中結(jié)點是我們需要處理的結(jié)點），所以只需要在中結(jié)點后面加入一個空結(jié)點就行了
中序遍歷：
先序遍歷：中左右
class Solution{ public:vector<int> preorderTraversal(TreeNode* root){vector<int> result;stack<TreeNode*> st;if(root !=NULL) st.push(root);while(!st.empty()){TreeNode* node = st.top(); //標(biāo)記操作，直到遇到NULLif(node!=NULL){//將該結(jié)點彈出，避免重復(fù)操作st.pop();//添加右結(jié)點if(node->right) st.push(node->right);//添加左結(jié)點if(node->left) st.push(node->left);//添加中結(jié)點st.push(node);//標(biāo)記st.push(NULL); }//只有遇到空結(jié)點的時候，才將下一個結(jié)點放入到結(jié)果中else{//彈出空結(jié)點st.pop();node = st.top();st.pop(); result.push_back(node->val);}}return result;} };后序遍歷：左右中
class Solution{ public:vector<int> postorderTraversal(TreeNode* root){vector<int> result;stack<TreeNode*> st;if(root !=NULL) st.push(root);while(!st.empty()){TreeNode* node = st.top(); //標(biāo)記操作，直到遇到NULLif(node!=NULL){//將該結(jié)點彈出，避免重復(fù)操作st.pop();//添加中結(jié)點st.push(node);//標(biāo)記st.push(NULL); //添加右結(jié)點if(node->right) st.push(node->right);//添加左結(jié)點if(node->left) st.push(node->left);}//只有遇到空結(jié)點的時候，才將下一個結(jié)點放入到結(jié)果中else{//彈出空結(jié)點st.pop();node = st.top();st.pop(); result.push_back(node->val);}}return result;} };總結(jié)：
這種方法比較好記憶，主要注意以下幾點
1、棧的特性入棧和出棧相反，所以如果想輸出順序為“左中右”，入棧順序必須為“右中左”
2、入棧的處理：可以將整個樹簡化為3個結(jié)點一組的多個子樹。每次循環(huán)處理的實際就是將這樣的3個結(jié)點按照規(guī)定的順序進(jìn)行入棧。
3、NULL結(jié)點的加入以及出棧規(guī)則的指定：
以中序遍歷為例，保證了當(dāng)左孩子作為棧頂元素時不會立即出棧，而是會將當(dāng)前的左孩子(棧頂元素)作為下次遍歷的父結(jié)點；接著按照規(guī)則順序入棧，直到當(dāng)前的左孩子作為父結(jié)點再無孩子時（此時是入棧規(guī)則為父結(jié)點、NULL結(jié)點），遇到NULL結(jié)點，進(jìn)行出棧。
5、二叉樹層序遍歷
1、leetcode102:二叉樹的層序遍歷
給你一個二叉樹，請你返回其按 層序遍歷 得到的節(jié)點值。 （即逐層地，從左到右訪問所有節(jié)點）。
示例：
二叉樹：[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其層次遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]
思考：
借用隊列來實現(xiàn)，【隊列先進(jìn)先出，符合一層一層遍歷的邏輯】
而棧先進(jìn)后出適合模擬深度優(yōu)先遍歷也就是遞歸地邏輯。
【這種層序遍歷的方式就是圖論中的廣度優(yōu)先遍歷，只不過用在了二叉樹上】
思考：
2、leetcode107:二叉樹的層序遍歷 II
給定一個二叉樹，返回其節(jié)點值自底向上的層次遍歷。 （即按從葉子節(jié)點所在層到根節(jié)點所在的層，逐層從左向右遍歷）
例如：
給定二叉樹 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其自底向上的層次遍歷為：
[
[15,7],
[9,20],
[3]
]
思路：在層序遍歷的基礎(chǔ)上進(jìn)行直接反轉(zhuǎn)
3、leetcode199:二叉樹的右視圖
給定一棵二叉樹，想象自己站在它的右側(cè)，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點值。
示例:
輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:
1 <—
/
2 3 <—
\
5 4 <—
思路：對層序遍歷的的結(jié)果的每個子層result取最后的一個，作為結(jié)果返回。
4、leetcode637:二叉樹的層平均值
給定一個非空二叉樹, 返回一個由每層節(jié)點平均值組成的數(shù)組。
示例 1：
輸入：
3
/
9 20
/
15 7
輸出：[3, 14.5, 11]
解釋：
第 0 層的平均值是 3 , 第1層是 14.5 , 第2層是 11 。因此返回 [3, 14.5, 11] 。
提示：
節(jié)點值的范圍在32位有符號整數(shù)范圍內(nèi)。
思考：層序遍歷中加入累加以及求均值操作
/*** 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:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL) que.push(root);vector<double> realresult;while(!que.empty()){//該層結(jié)點元素個數(shù) = 該層隊列元素int size = que.size();vector<int> vec;double sum = 0;//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結(jié)點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結(jié)果que.pop();vec.push_back(node->val);sum+=vec[i];//將左右孩子結(jié)點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}realresult.push_back(sum /size);}return realresult;} };5、leetcode429:N叉樹的層序遍歷
給定一個 N 叉樹，返回其節(jié)點值的層序遍歷。 (即從左到右，逐層遍歷)。
例如，給定一個 3叉樹 :
返回其層序遍歷:
[
[1],
[3,2,4],
[5,6]
]
說明:
樹的深度不會超過 1000。
樹的節(jié)點總數(shù)不會超過 5000。
思考：與二叉樹層序遍歷方法一樣，不過子結(jié)點的個數(shù)不定
6、leetcode515. 在每個樹行中找最大值
您需要在二叉樹的每一行中找到最大的值。
示例：
輸入:
1
/
3 2
/ \ \
5 3 9
輸出: [1, 3, 9]
思考：層序遍歷，然后在每層中找最大值
7、leetcode116. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針
給定一個完美二叉樹，其所有葉子節(jié)點都在同一層，每個父節(jié)點都有兩個子節(jié)點。二叉樹定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側(cè)節(jié)點。如果找不到下一個右側(cè)節(jié)點，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。
示例：
解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個 next 指針，以指向其下一個右側(cè)節(jié)點，如圖 B 所示。
提示：
你只能使用常量級額外空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的棧空間不算做額外的空間復(fù)雜度。
思考：層序遍歷，只不過在單層遍歷的時候記錄本層的頭部節(jié)點，然后在遍歷的時候讓前一個節(jié)點指向本節(jié)點。
/* // Definition for a Node. class Node { public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {} }; */class Solution { public:Node* connect(Node* root) {queue<Node*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size = que.size();Node* node;Node* Prenode;for(int i =0;i<size;i++){//每層第一個元素元素if(i==0){Prenode =que.front();que.pop();node = Prenode;}//非每層第一個結(jié)點else{node = que.front();que.pop();//將此結(jié)點與上一個結(jié)點連在一起Prenode->next = node;Prenode = node; }//將左右孩子結(jié)點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}Prenode->next =NULL;}return root;} };8、leetcode117. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針 II（遇上一題思路代碼一致）
給定一個二叉樹
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側(cè)節(jié)點。如果找不到下一個右側(cè)節(jié)點，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。
進(jìn)階：
你只能使用常量級額外空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的棧空間不算做額外的空間復(fù)雜度。
9、104. 二叉樹的最大深度
思路：層序遍歷，每層對一個變量++即可
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點到最遠(yuǎn)葉子節(jié)點的最長路徑上的節(jié)點數(shù)。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例：
給定二叉樹 [3,9,20,null,null,15,7]，
/
9 20
/
15 7
返回它的最大深度 3 。
10、111. 二叉樹的最大深度
給定一個二叉樹，找出其最小深度。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。
示例:
給定二叉樹 [3,9,20,null,null,15,7],
3/
9 20
/
15 7
返回它的最小深度 2.
思考：層序遍歷，若當(dāng)前層有一個結(jié)點的左孩子和右孩子均無則可以確定最小深度。
不過這個思路的效率很低
總結(jié)
以上是生活随笔為你收集整理的二叉树笔记（深度遍历与广度遍历+13道leetcode题目(深度3道、广度10道)）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： “开封述天爵”下一句是什么
- 下一篇： 兔子肉多少钱一斤啊？