二叉樹筆記（深度遍歷與廣度遍歷+13道leetcode題目(深度3道、廣度10道)）

本文章為結合leetcode題目以及公眾號“代碼隨想錄”的文章所做的筆記！
感覺代碼隨想錄的題目整理真的很好，比自己盲目刷題好很多。

目錄

  • 1、二叉樹小記
    • 1、滿二叉樹與完全二叉樹
    • 2、二叉搜索樹
    • 3、平衡二叉搜索樹AVL
    • 4、二叉樹存儲方式
    • 5、二叉樹遍歷方式
    • 6、二叉樹的定義
  • 2、二叉樹深度優先遍歷遞歸算法書寫
    • 1、leetcode144題：
    • 2、leetcode145題：
    • 3、leetcode94題：
  • 3、二叉樹深度優先遍歷迭代算法書寫
    • 1、先序遍歷（迭代法）
    • 2、中序遍歷（迭代法）
    • 3、后序遍歷（迭代法）
  • 4、二叉樹深度優先遍歷迭代算法格式統一
  • 5、二叉樹層序遍歷
    • 1、leetcode102:二叉樹的層序遍歷
    • 2、leetcode107:二叉樹的層序遍歷 II
    • 3、leetcode199:二叉樹的右視圖
    • 4、leetcode637:二叉樹的層平均值
    • 5、leetcode429:N叉樹的層序遍歷
    • 6、leetcode515. 在每個樹行中找最大值
    • 7、leetcode116. 填充每個節點的下一個右側節點指針
    • 8、leetcode117. 填充每個節點的下一個右側節點指針 II（遇上一題思路代碼一致）
    • 9、104. 二叉樹的最大深度
    • 10、111. 二叉樹的最大深度

1、二叉樹小記

1、滿二叉樹與完全二叉樹

滿二叉樹：深度為k，有2的k-1個節點的二叉樹。
完全二叉樹：除了最底層節點可能沒填滿外，其余每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若干位置。若最底層為第h層，則該層包含1~2h個節點。

2、二叉搜索樹

二叉搜索樹是有數值的，是一個有序樹。
它的特點：

1、若它的左子樹不空，則左子樹所有結點的值均小于它根結點的值
2、若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值
3、它的左右子樹也分別為二叉排序樹

3、平衡二叉搜索樹AVL

AVL是一棵空數或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。
C++中map、set、multimap、multiset的底層實現都是平衡二叉搜索樹，所以map、set的增刪操作時間復雜度都是logn。
而unordered_map、unordered_set、unordered_map、unordered_map底層實現是哈希表。

4、二叉樹存儲方式

鏈表存儲與數組存儲。
數組存儲二叉樹遍歷：如果父節點的數組下標是i，那么它的左孩子就是i2+1,右孩子就是i2+2.

5、二叉樹遍歷方式

有兩種遍歷方式：
1、深度優先遍歷：先往深走，遇到葉子結點再往回走
分為：前序遍歷、中序遍歷、后序遍歷
這里的前中后，指的是中間結點的遍歷順序
前序遍歷：中、左、右
中序遍歷：左、中、右
后序遍歷：左、右、中
深度優先遍歷使用遞歸是比較方便的，可以借助棧使用非遞歸方式實現。

2、廣度優先遍歷：一層一層的去遍歷
分為：層次遍歷
廣度優先遍歷一般使用隊列實現，利用了隊列的先進先出的特點。這樣才能一層一層的來遍歷二叉樹。

6、二叉樹的定義

二叉樹的定義和鏈表差不多，多了一個指針

struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x),left(NULL),right(NULL) {}
};

2、二叉樹深度優先遍歷遞歸算法書寫

遞歸算法的三個要素：
1、確定遞歸函數的參數和返回值

若是在遞歸過程中需要處理某個參數，就在遞歸函數里面加上這個參數。
明確每次遞歸地返回值是什么，進而確定遞歸函數的返回類型

2、確定終止條件

1、如果在遞歸算法運行過程中出現棧溢出，大概率是終止條件寫的不對
2、操作系統也是用一個棧的結構來保存每一層遞歸地信息，如果遞歸沒有終止，操作系統的內存棧必然就會溢出

3、確定單層遞歸邏輯

確定每一層遞歸需要處理的信息。在這里也會重復調用自己來實現遞歸地過程

以前序遍歷為例：
1、因為要打印出前序遍歷結點的數值，所以參數里需要傳入vector放在結點里的數據。沒有返回值

void traversal(TreeNode* cur ,vector<int>& vec)

2、在遞歸過程中，如何算是遞歸結束？如果當前遍歷的結點是空的，那么本層遞歸就結束了

if(cur == NULL) return;

3、前序遍歷是中左右的循序，所以在單層遞歸中就要先取出中結點的數據

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]

/*** 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;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;}
};

2、leetcode145題：

給定一個二叉樹，返回它的 后序 遍歷。
示例:
輸入: [1,null,2,3]
1

2
/
3
輸出: [3,2,1]

/*** 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);traversal(cur->right,vec);vec.push_back(cur->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};

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、二叉樹深度優先遍歷迭代算法書寫

原理：為什么可以使用迭代法(非遞歸地方式)來實現二叉樹的前后中序遍歷？
遞歸地實現就是：每一次遞歸調用都會把函數的局部變量、參數值和返回地址等壓入調用棧中，
然后遞歸返回的時候，從棧頂彈出上一次遞歸的各項參數，所以這就是遞歸為什么可以返回上一層位置的原因。

1、先序遍歷（迭代法）

前序遍歷：中左右；每次處理的是中間結點，先將根結點放入棧中，然后將右孩子放入棧中，再加入左孩子。
為什么要先加入有孩子，再加入左孩子？
這樣出棧的時候才是中左右的順序。
順序如下：
在這里插入圖片描述

class Solution{
public:vector<int> preorderTraversal(TreeNode* root){stack<TreeNode*> st;		//構建一個棧vector<int> result;st.push(root);			//先將根結點壓入棧中while(!st.empty()){			//當棧中還有元素時TreeNode* node = st.top();	//將棧頂元素賦給新結點	st.pop();					//將棧頂元素出棧if(node !=NULL) result.push_back(node->val);	//如果這個結點不為空，將值賦給resultelse continue;									//否則繼續，（也就是說如果結點為空不賦值）st.push(node->right);		//將該中結點的右孩子壓入棧中st.push(node->left);		//將該結點中的左孩子壓入棧中}return result;}
};

2、中序遍歷（迭代法）

注意，前序遍歷的迭代法思路不能直接套用到中序遍歷上。
在迭代的過程中有兩個操作:
1、【處理】將元素放入result數組
2、【訪問】遍歷結點
前序遍歷中：遍歷的順序是中左右。
先訪問中間結點，先處理中間結點
要訪問的元素和要處理的元素的順序一致，都是中間結點。
而中序遍歷，遍歷順序為左中右。
先訪問二叉樹頂部結點，然后一層一層向下訪問，直到到達樹左面的最底部，再開始處理結點（再把結點的數值放到result數組中）；
這就導致了處理順序和訪問順序不一致
所以在使用迭代 法時，需要借用指針的遍歷來幫助訪問結點，使用棧來處理結點上的元素。
在這里插入圖片描述

class Solution{
public:vector<int> inorderTraversal(TreeNode* root){vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while(!st.empty() || cur!=NULL){if(cur!=NULL){st.push(cur);cur = cur->left;    //先一直都是從左結點深入，直到某一個結點的左孩子為NULL}//如果該點是父結點的左孩子，且指向空，則將cur指向它的父結點（為最深的左結點），然后將父結點出棧，將值賦給結果數組，再將指針指向此父結點的右孩子（這樣保證了左中右的遍歷順序）else{cur = st.top();st.pop();result.push_back(cur->val);cur = cur->right;}          }return result;}
};

3、后序遍歷（迭代法）

后序遍歷：左右中。
先序遍歷：中左右。
我們只需要調整一下先序遍歷的代碼順序，變為中右左的遍歷順序。
然后反轉result數組，輸出結果就是左右中。

/*** 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:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;		//構建一個棧vector<int> result;st.push(root);			//先將根結點壓入棧中while(!st.empty()){			//當棧中還有元素時TreeNode* node = st.top();	//將棧頂元素賦給新結點	st.pop();					//將棧頂元素出棧if(node !=NULL) result.push_back(node->val);	//如果這個結點不為空，將值賦給resultelse continue;									//否則繼續，（也就是說如果結點為空不賦值）st.push(node->left);		//將該中結點的左孩子壓入棧中st.push(node->right);		//將該結點中的右孩子壓入棧中}//反轉resultreverse(result.begin(),result.end());return result;}
};

4、二叉樹深度優先遍歷迭代算法格式統一

之前迭代法例子中提到無法同時解決訪問節點（遍歷）和處理結點（將結點放入結果）不一致的情況。
解決方法：
將訪問的結點放入棧中，把要處理的結點也放入棧中，但是要做標記
標記方法：將要處理的結點放入棧中之后，緊接著放入一個空指針作為標記
將訪問的結點直接加入到棧中，但是如果是處理的結點則后面放入一個空結點，這樣只有空結點彈出的時候才將下一個結點放進結果集。
如何知道該訪問的結點是我們需要處理的結點？（中結點是我們需要處理的結點），所以只需要在中結點后面加入一個空結點就行了
中序遍歷：

class Solution{
public:vector<int> inorderTraversal(TreeNode* root){vector<int> result;stack<TreeNode*> st;if(root !=NULL) st.push(root);while(!st.empty()){TreeNode* node = st.top();  //標記操作，直到遇到NULLif(node!=NULL){//將該結點彈出，避免重復操作st.pop();//添加右結點if(node->right) st.push(node->right);//添加中結點st.push(node);//標記st.push(NULL); //添加左結點if(node->left) st.push(node->left);}//只有遇到空結點的時候，才將下一個結點放入到結果中else{//彈出空結點st.pop();node = st.top();st.pop();   result.push_back(node->val);}}return result;}
};

先序遍歷：中左右

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();  //標記操作，直到遇到NULLif(node!=NULL){//將該結點彈出，避免重復操作st.pop();//添加右結點if(node->right) st.push(node->right);//添加左結點if(node->left) st.push(node->left);//添加中結點st.push(node);//標記st.push(NULL); }//只有遇到空結點的時候，才將下一個結點放入到結果中else{//彈出空結點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();  //標記操作，直到遇到NULLif(node!=NULL){//將該結點彈出，避免重復操作st.pop();//添加中結點st.push(node);//標記st.push(NULL); //添加右結點if(node->right) st.push(node->right);//添加左結點if(node->left) st.push(node->left);}//只有遇到空結點的時候，才將下一個結點放入到結果中else{//彈出空結點st.pop();node = st.top();st.pop();   result.push_back(node->val);}}return result;}
};

總結：

這種方法比較好記憶，主要注意以下幾點
1、棧的特性入棧和出棧相反，所以如果想輸出順序為“左中右”，入棧順序必須為“右中左”
2、入棧的處理：可以將整個樹簡化為3個結點一組的多個子樹。每次循環處理的實際就是將這樣的3個結點按照規定的順序進行入棧。
3、NULL結點的加入以及出棧規則的指定：
以中序遍歷為例，保證了當左孩子作為棧頂元素時不會立即出棧，而是會將當前的左孩子(棧頂元素)作為下次遍歷的父結點；接著按照規則順序入棧，直到當前的左孩子作為父結點再無孩子時（此時是入棧規則為父結點、NULL結點），遇到NULL結點，進行出棧。

5、二叉樹層序遍歷

1、leetcode102:二叉樹的層序遍歷

給你一個二叉樹，請你返回其按 層序遍歷 得到的節點值。 （即逐層地，從左到右訪問所有節點）。
示例：
二叉樹：[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其層次遍歷結果：

[
[3],
[9,20],
[15,7]
]
思考：
借用隊列來實現，【隊列先進先出，符合一層一層遍歷的邏輯】
而棧先進后出適合模擬深度優先遍歷也就是遞歸地邏輯。
【這種層序遍歷的方式就是圖論中的廣度優先遍歷，只不過用在了二叉樹上】
思考：
在這里插入圖片描述

/*** 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<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL) que.push(root);vector<vector<int>> result;while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();vector<int> vec;//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();vec.push_back(node->val);//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(vec);}return result;}
};

2、leetcode107:二叉樹的層序遍歷 II

給定一個二叉樹，返回其節點值自底向上的層次遍歷。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）
例如：
給定二叉樹 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其自底向上的層次遍歷為：

[
[15,7],
[9,20],
[3]
]
思路：在層序遍歷的基礎上進行直接反轉

/*** 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<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL) que.push(root);vector<vector<int>> result;while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();vector<int> vec;//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();vec.push_back(node->val);//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(vec);}//將層序遍歷反轉一下結果reverse(result.begin(),result.end());return result;}
};

3、leetcode199:二叉樹的右視圖

給定一棵二叉樹，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。
示例:
輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:
1 <—
/
2 3 <—
\
5 4 <—
思路：對層序遍歷的的結果的每個子層result取最后的一個，作為結果返回。

/*** 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<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL) que.push(root);vector<int> realresult;while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();vector<int> vec;//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();vec.push_back(node->val);//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}realresult.push_back(vec[size-1]);}return realresult;}
};

4、leetcode637:二叉樹的層平均值

給定一個非空二叉樹, 返回一個由每層節點平均值組成的數組。
示例 1：
輸入：
3
/
9 20
/
15 7
輸出：[3, 14.5, 11]
解釋：
第 0 層的平均值是 3 , 第1層是 14.5 , 第2層是 11 。因此返回 [3, 14.5, 11] 。
提示：
節點值的范圍在32位有符號整數范圍內。

思考：層序遍歷中加入累加以及求均值操作

/*** 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()){//該層結點元素個數 = 該層隊列元素int size = que.size();vector<int> vec;double sum = 0;//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();vec.push_back(node->val);sum+=vec[i];//將左右孩子結點入隊列，作為下一層的元素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 叉樹，返回其節點值的層序遍歷。 (即從左到右，逐層遍歷)。
例如，給定一個 3叉樹 :
返回其層序遍歷:
[
[1],
[3,2,4],
[5,6]
]
說明:
樹的深度不會超過 1000。
樹的節點總數不會超過 5000。
思考：與二叉樹層序遍歷方法一樣，不過子結點的個數不定

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;if(root!=NULL) que.push(root);vector<vector<int>> result;while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();vector<int> vec;//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){Node* node = que.front();//將隊首元素送入該層結果que.pop();vec.push_back(node->val);//將所有孩子結點入隊列，作為下一層的元素for(int j=0;j<node->children.size();j++){if(node->children[j]) que.push(node->children[j]);}}result.push_back(vec);}return result;}
};

6、leetcode515. 在每個樹行中找最大值

您需要在二叉樹的每一行中找到最大的值。
示例：
輸入:
1
/
3 2
/ \ \
5 3 9

輸出: [1, 3, 9]
思考：層序遍歷，然后在每層中找最大值

/*** 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:vector<int> largestValues(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL) que.push(root);vector<int> result;while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();int max=-2147483648;    //(最小值)vector<int> vec;//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();vec.push_back(node->val);if(max<=node->val) max = node->val;//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(max);}return result;}
};

7、leetcode116. 填充每個節點的下一個右側節點指針

給定一個完美二叉樹，其所有葉子節點都在同一層，每個父節點都有兩個子節點。二叉樹定義如下：

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。
初始狀態下，所有 next 指針都被設置為 NULL。

示例：
在這里插入圖片描述
在這里插入圖片描述
解釋：給定二叉樹如圖 A 所示，你的函數應該填充它的每個 next 指針，以指向其下一個右側節點，如圖 B 所示。
提示：
你只能使用常量級額外空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的棧空間不算做額外的空間復雜度。

思考：層序遍歷，只不過在單層遍歷的時候記錄本層的頭部節點，然后在遍歷的時候讓前一個節點指向本節點。

/*
// 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;}//非每層第一個結點else{node = que.front();que.pop();//將此結點與上一個結點連在一起Prenode->next = node;Prenode = node; }//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}Prenode->next =NULL;}return root;}
};

8、leetcode117. 填充每個節點的下一個右側節點指針 II（遇上一題思路代碼一致）

給定一個二叉樹
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。
初始狀態下，所有 next 指針都被設置為 NULL。

進階：
你只能使用常量級額外空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的棧空間不算做額外的空間復雜度。
在這里插入圖片描述

9、104. 二叉樹的最大深度

思路：層序遍歷，每層對一個變量++即可
給定一個二叉樹，找出其最大深度。

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

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

3

/
9 20
/
15 7
返回它的最大深度 3 。

/*** 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) {queue<TreeNode*> que;if(root!=NULL) que.push(root);int result=0;while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();//將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result++;}return result; }
};

10、111. 二叉樹的最大深度

給定一個二叉樹，找出其最小深度。

最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。

說明: 葉子節點是指沒有子節點的節點。

示例:

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

3

/
9 20
/
15 7
返回它的最小深度 2.
思考：層序遍歷，若當前層有一個結點的左孩子和右孩子均無則可以確定最小深度。
不過這個思路的效率很低

/*** 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:int minDepth(TreeNode* root) {queue<TreeNode*> que;if(root!=NULL) que.push(root);int result=0;int break_flag=0;while(!que.empty()){//該層結點元素個數 = 該層隊列元素int size = que.size();//這里要使用固定大小的size，不能使用que.size(),因為在處理中que.size是不斷變化的//將這層元素送入隊列中并依次從隊首向隊尾將元素出隊列，每個元素出隊列的同時又將其不為空的子結點送入隊列for(int i =0;i<size;i++){TreeNode* node = que.front();//將隊首元素送入該層結果que.pop();if(!node->left && !node->right){return result+1;} //將左右孩子結點入隊列，作為下一層的元素if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result++;}return result;  }
};

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/378051.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/378051.shtml
英文地址，請注明出處：http://en.pswp.cn/news/378051.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

ZZ的計算器

ZZ的計算器

Problem Description ZZ自從上大學以來&#xff0c;腦容量就是以SB計算的&#xff0c;這個吃貨竟然連算術運算也不會了&#xff0c;可是當今的計算機可是非常強大的&#xff0c;作為ACMer&#xff0c; 幾個簡單的算術又算得了什么呢&#xff1f;可是該怎么做呢&#xff1f;ZZ只…
閱讀更多...
kotlin 覆蓋屬性_Kotlin程序| 方法覆蓋的示例

kotlin 覆蓋屬性_Kotlin程序| 方法覆蓋的示例

kotlin 覆蓋屬性方法重載 (Method Overriding) Method overriding allows derived class has the same function name and signature as the base class 方法重寫允許派生類具有與基類相同的函數名稱和簽名 By method overriding we can provide different implementation into…
閱讀更多...
對視頻中的特征顏色物體(青色水杯)進行跟蹤

對視頻中的特征顏色物體(青色水杯)進行跟蹤

方法一&#xff1a;目標物體白色&#xff0c;其余黑色 import cv2 import numpy as npdef extrace_object():capture cv2.VideoCapture("G:/Juptyer_workspace/study/data/yy.mp4")while(True):ret,frame capture.read()if retFalse:breakhsv cv2.cvtColor(frame…
閱讀更多...
Android實現號碼歸屬地查詢

Android實現號碼歸屬地查詢

我們通過發送XML訪問 WebService就可以實現號碼的歸屬地查詢&#xff0c;我們可以使用代理服務器提供的XML的格式進行設置&#xff0c;然后請求提交給服務器&#xff0c;服務器根據請求就會返回給一個XML&#xff0c;XML中就封裝了我們想要獲取的數據。 發送XML 1.通過URL封裝路…
閱讀更多...
如何從 Datagrid 中獲得單元格的內容與 使用值轉換器進行綁定數據的轉換IValueConverter...

如何從 Datagrid 中獲得單元格的內容與 使用值轉換器進行綁定數據的轉換IValueConverter...

一、如何從 Datagrid 中獲得單元格的內容 DataGrid 屬于一種 ItemsControl, 因此&#xff0c;它有 Items 屬性并且用ItemContainer 封裝它的 items. 但是&#xff0c;WPF中的DataGrid 不同于Windows Forms中的 DataGridView。 在DataGrid的Items集合中&#xff0c;DataGridRow…
閱讀更多...
【C++ grammar】常量、指針、Usage of using, typedef, and #define

【C++ grammar】常量、指針、Usage of using, typedef, and #define

目錄1、常量 &#xff08;Constant&#xff09;2、指針&#xff08;Pointer&#xff09;3、Usage of using, typedef, and #define1、常量 &#xff08;Constant&#xff09; 常量是程序中一塊數據&#xff0c;這個數據一旦聲明后就不能被修改了。 如果這塊數據有一個名字&am…
閱讀更多...
斯威夫特山地車_斯威夫特| 兩個數字相加的程序

斯威夫特山地車_斯威夫特| 兩個數字相加的程序

斯威夫特山地車In this program, we will have an idea - how two numbers can be added and displayed as the output on the screen? 在此程序中&#xff0c;我們將有一個想法- 如何將兩個數字相加并顯示為屏幕上的輸出 &#xff1f; Open XCode terminal and type the fol…
閱讀更多...
四、色彩空間

四、色彩空間

一、色彩空間 1、什么是色彩空間&#xff1f; 色彩空間是定義的顏色范圍。 2、常見的色彩空間有哪些&#xff1f; ①RGB ②HSV 在OpenCV中&#xff0c;Hue的值為0~180&#xff0c;之所以不是360是因為&#xff0c;8位存不下&#xff0c;故進行歸一化操作&#xff0c;使得H…
閱讀更多...
Oracle LOB 詳解

Oracle LOB 詳解

一. 官方說明Oracle 11gR2 文檔&#xff1a;LOB Storagehttp://download.oracle.com/docs/cd/E11882_01/appdev.112/e18294/adlob_tables.htm#ADLOB45267Oracle 10gR2 文檔&#xff1a;LOBs in Tableshttp://download.oracle.com/docs/cd/B19306_01/appdev.102/b14249/adlob_t…
閱讀更多...
FIFA的完整形式是什么？

FIFA的完整形式是什么？

國際足聯&#xff1a;國際足球聯合會 (FIFA: Federation Internationale de Football Association) FIFA is an abbreviation of the "Federation Internationale de Football Association" in French. It is also known as the International Federation of Associa…
閱讀更多...
POJ 1654 Area

POJ 1654 Area

題意&#xff1a;從原點出發&#xff0c;沿著8個方向走&#xff0c;每次走1個點格或者根號2個點格的距離&#xff0c;最終回到原點&#xff0c;求圍住的多邊形面積。分析&#xff1a;直接記錄所經過的點&#xff0c;然后計算多邊形面積。注意&#xff0c;不用先保存所有的點&am…
閱讀更多...
【C++ grammar】重載、內聯、變量作用域、帶默認參數的函數

【C++ grammar】重載、內聯、變量作用域、帶默認參數的函數

目錄1、變量的作用域1. 變量的作用域分類2. Unary Scope Resolution (一元作用域解析運算符)2、重載函數3、帶有默認參數值的函數4、重載函數 VS 帶有默認參數值的函數5、內聯函數&#xff08;Inline Function&#xff09;1. 普通函數的優缺點2. 使用內聯函數3. 定義內聯函數4.…
閱讀更多...
五、像素運算

五、像素運算

一、相關概念 1、算術運算 Ⅰ加減乘除 Ⅱ調節亮度 Ⅲ調整對比度 2、邏輯運算 Ⅰ與或非 Ⅱ遮罩層控制 二、圖像算術運算(加減乘除均值方差) 其中圖像的加減乘除需要保證兩張圖像的大小相同 import cv2 import numpy as npdef add(src1,src2):dst cv2.add(src1,src2)cv2.im…
閱讀更多...
創建bootstrap項目_使用Bootstrap創建第一個網頁

創建bootstrap項目_使用Bootstrap創建第一個網頁

創建bootstrap項目使用Bootstrap創建第一個網頁 (Create First Webpage with Bootstrap) In the previous article, we learned "how to setup bootstrap?" for a web project. If you haven’t gone through that, it is recommended to read it. Now, in this art…
閱讀更多...
Chaikin Curve(球面插值)

Chaikin Curve(球面插值)

在兩條折線間完成平滑的過渡是 用畫布做UI 或者做類似地圖編輯器一類的工作的 很常見的任務。 怎么樣化方為圓是決定工作效率的很重要的因素。&#xff08;當需要編輯的曲線多起來&#xff0c; 復雜起來的時候&#xff0c;這會是件相當繁重的工作&#xff09; 最容易想到的莫非…
閱讀更多...
【2020 電設G題 圖像題解】

【2020 電設G題 圖像題解】

博主聯系方式： QQ:1540984562 QQ交流群：892023501 群里會有往屆的smarters和電賽選手，群里也會不時分享一些有用的資料，有問題可以在群里多問問。 2022.3.10新增訂閱通知 近期把此專欄設置為了付費模式，可以直接花9.9買這個專欄，買了就可以直接這個專欄的所有文章了。后…
閱讀更多...
六、ROI和泛洪填充

六、ROI和泛洪填充

一、ROI ROI&#xff1a;region of interest&#xff0c;即感興趣區域。 一般主要通過numpy來獲取ROI 將某區域轉變為灰色圖片再覆蓋原圖像 import cv2 import numpy as npsrc cv2.imread(r"G:\Juptyer_workspace\study\opencv\opencv3\a1.jpg") cv2.imshow(&quo…
閱讀更多...
VS2005 there is no source code available for the current location 解決方案

VS2005 there is no source code available for the current location 解決方案

1.首先試最常規的方法&#xff1a;Clean and then rebuild solution&#xff0c;但是沒有解決 2.進入Tools>Options,選擇Debugging>General 卻掉 Enable address-level debugging 選項&#xff0c;在去掉 Require source files to exactly match the original version. O…
閱讀更多...
django 靜態數據_如何在Django中使用靜態數據？

django 靜態數據_如何在Django中使用靜態數據？

django 靜態數據Static Data means those data items that we cannot want to change, we want to use them as it is like audio, video, images, files etc. 靜態數據是指我們不想更改的數據項&#xff0c;我們想像音頻&#xff0c;視頻&#xff0c;圖像&#xff0c;文件等那…
閱讀更多...
Leetcode226. 翻轉二叉樹(遞歸、迭代、層序三種解法)

Leetcode226. 翻轉二叉樹(遞歸、迭代、層序三種解法)

目錄題目1、層序法&#xff1a;2、遞歸法&#xff1a;1、先序遍歷&#xff08;中左右&#xff09;2、后序遍歷&#xff08;左右中&#xff09;3、遞歸中序遍歷為什么不行&#xff08;左中右&#xff09;3、迭代法&#xff1a;1、先序遍歷2、中序遍歷3、后序遍歷為什么迭代法的中…
閱讀更多...
最新文章

Copyright @ 2022~2023