LeetCode刷題day15-有解無憂

演算法打卡第十五天,今天你刷題了嗎
😄😄😄😄😄😄😄😄😄😄
😃😃😃😃😃😃😃😃😃😃
💓💓💓大家一起來刷題!💓💓💓
😍😍😍😍😍😍😍😍😍😍
😘😘😘😘😘😘😘😘😘😘

請添加圖片描述

144. 二叉樹的前序遍歷

94. 二叉樹的中序遍歷

145. 二叉樹的后序遍歷

思路分析:

遞回和迭代兩種方法都可進行處理

方法一:遞回

參考代碼

//前序
void preorder(TreeNode* T) {
	if(T) {
		V.push_back(T->val);
		preorder(T->left);
		preorder(T->right);
	}
}
//中序
void inorder(TreeNode* T) {
	if(T) {	
		inorder(T->left);
		V.push_back(T->val);
		inorder(T->right);
	}
}
//后序
void postorder(TreeNode* T) {
	if(T) {
		postorder(T->left);
		postorder(T->right);
		V.push_back(T->val);
	}
}

vector<int> V;
vector<int> xxxorderTraversal(TreeNode* root) {
	xxxorder(root);
	return V;
}

方法二:迭代

本質上是在模擬遞回，因為在遞回的程序中使用了系統堆疊，所以在迭代的解法中常用Stack來模擬系統堆疊，

以前序遍歷為例

首先我們應該創建一個Stack用來存放節點，首先我們想要列印根節點的資料，此時Stack里面的內容為空，所以我們優先將頭結點加入Stack，然后列印，
之后我們應該先列印左子樹，然后右子樹，所以先加入Stack的就是右子樹，然后左子樹，

此時你能得到的流程如下:

在這里插入圖片描述

參考代碼2

//迭代做法. 
vector<int> preorderTraversal(TreeNode* root) {	
	if(root==null){
		return {};
	}
	vector<int> V;
	TreeNode* cur = root; 
	stack<TreeNode*> S;
	S.push(root); 	
	while(!stack.empty()){
		TreeNode* node = S.top();
		S.pop();
		V.push_back(node->val);//通過改變該陳述句的順序,來決定是先序,中序和后序..
		if(node->right != NULL){
			S.push(node->right);
		} 
		if(node->left!=NULL){
			S.push(node->left);
		}
	}
	return V;
}

請添加圖片描述

102. 二叉樹的層序遍歷

給你一個二叉樹，請你回傳其按層序遍歷得到的節點值，（即逐層地，從左到右訪問所有節點），

示例：

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

    3
   / \
  9  20
    /  \
   15   7
回傳其層序遍歷結果：

[
  [3],
  [9,20],
  [15,7]
]

思路分析:

參考 BFS的使用場景總結

參考代碼

#include<bits/stdc++.h>
using namespace std;

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 
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) {}
};

vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> V;
	queue<TreeNode*> Q;
	if(root==NULL){
		return {};
	}
	Q.push(root);
	while(!Q.empty()){
		int n  = Q.size();//計算當前層元素的個數 
		vector<int> v;
		for(int i = 0;i <n;i++){//將當前層元素彈出放到v中. 
			TreeNode* node = Q.front();
			Q.pop();
		
			v.push_back(node->val);
			if(node->left){
				Q.push(node->left);
			}
			if(node->right){
				Q.push(node->right);
			}			
		}
		V.push_back(v); 
	}
	return V;
}

請添加圖片描述

104. 二叉樹的最大深度

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

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

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

示例：

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

    3
   / \
  9  20
    /  \
   15   7
回傳它的最大深度 3 ，

參考代碼

int maxDepth(TreeNode* root) {
	int m,n;
	if(root){
		return 0;
	}else{
		m = maxDepth(root->left);//遞回計算左子樹深度 
		n = maxDepth(root->right);//遞回計算右子樹深度 
		if(m>n){
			return m+1;//回傳左右子樹的最大值+1 
		}else{
			return n+1;
		}
	}

}

請添加圖片描述

101. 對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的，

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的，

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

方法一:遞回

根據題目的描述，鏡像對稱，就是左右兩邊相等，也就是左子樹和右子樹是相當的，
注意這句話，左子樹和右子相等，也就是說要遞回的比較左子樹和右子樹，

我們將根節點的左子樹記做 left，右子樹記做 right，比較 left 是否等于 right，不等的話直接回傳就可以了，
如果相當，比較 left 的左節點和 right 的右節點，再比較 left 的右節點和 right 的左節點

比如看下面這兩個子樹(他們分別是根節點的左子樹和右子樹)，能觀察到這么一個規律：

左子樹 2 的左孩子 == 右子樹 2 的右孩子
左子樹 2 的右孩子 == 右子樹 2 的左孩子

   2         2
   / \       / \
  3   4     4   3
 / \ / \   / \ / \
8  7 6  5 5  6 7  8

根據上面資訊可以總結出遞回函式的兩個條件：
終止條件：

left 和 right 不等，或者 left 和 right 都為空
遞回的比較 left.left 和 right.right，遞回比較 left.right 和 right.left
動態圖如下:

時間復雜度:O(n)，因為要遍歷 n 個節點
空間復雜度是 O(n),空間復雜度是遞回的深度，也就是跟樹高度有關，最壞情況下樹變成一個鏈表結構，高度是n，

參考代碼:

#include<bits/stdc++.h>
using namespace std;
//https://leetcode-cn.com/problems/symmetric-tree/
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) {}
};
// 遞回+dfs 
bool dfs(TreeNode* left,TreeNode* right){
	//遞回終止的條件
	if(left==NULL&&right==NULL){
		return true;//肯定對稱 
	} 
	if(left==NULL||right==NULL){
		return false;
	} 
	if(left->val!=right->val){
		return false;
	} 
	return dfs(left->left,right->right)&&dfs(left->right,right->left);
}

bool isSymmetric(TreeNode* root) {
	if(root==NULL){
		return true;
	}
	//呼叫遞回函式,比較左節點和右節點
	return dfs(root->left,root->right); 
}





int main()
{
	return 0;
}

方法二:迭代

回想下遞回的做法:
當兩個子樹的根節點相等時，就比較:左子樹的 left 和右子樹的 right.
現在我們改用佇列來實作，思路如下：

首先從佇列中拿出兩個節點(left 和 right)比較
將 left 的 left 節點和 right 的 right 節點放入佇列
將 left 的 right 節點和 right 的 left 節點放入佇列

時間復雜度是O(n)，空間復雜度是 O(n)

在這里插入圖片描述

參考代碼:

#include<bits/stdc++.h>
using namespace std;
//https://leetcode-cn.com/problems/symmetric-tree/
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) {}
};
// 迭代 
bool isSymmetric(TreeNode* root) {
	if(root==NULL || (root->left==NULL && root->right==NULL)){
		return true;
	} 
	//用佇列保存左右節點
	queue<TreeNode*> Q;
	Q.push(root->left);
	Q.push(root->right);
	while(!Q.empty()){
		TreeNode* left = Q.front();
		Q.pop();
		TreeNode *right = Q.front();
		Q.pop();
		if(left==NULL&&right==NULL){
//			return true;
			continue;//進行下一組節點的判斷 
		}
		if(left==NULL||right==NULL){
			return false;
		}
		if(left->val!=right->val){
			return false;
		}
		//將左節點的左孩子,右節點的右孩子放入佇列.
		Q.push(left->left);
		Q.push(right->right); 
		//將左節點的右孩子,右節點的左孩子放入佇列 
		Q.push(left->right);
		Q.push(right->left);
	}
	return true;
}

😜😜😜😜😜 大家卷起來! 😝😝😝😝😝
請添加圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352142.html

標籤：其他

上一篇：【C++學習】——（二）編譯與鏈接

下一篇：LeetCode：598. 范圍求和 II————簡單