今天學(xué)習(xí)的文章和視頻鏈接
https://www.bilibili.com/video/BV1ue4y1Y7Mf/?vd_source=8272bd48fee17396a4a1746c256ab0ae
102 二叉樹(shù)的層序遍歷
給你二叉樹(shù)的根節(jié)點(diǎn) root ，返回其節(jié)點(diǎn)值的 層序遍歷 。 （即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn)）。
示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]
示例 2：
輸入：root = [1]
輸出：[[1]]
示例 3：
輸入：root = []
輸出：[]
提示：
樹(shù)中節(jié)點(diǎn)數(shù)目在范圍 [0, 2000] 內(nèi)
-1000 <= Node.val <= 1000
題目分析
層序遍歷一個(gè)二叉樹(shù)。就是從左到右一層一層的去遍歷二叉樹(shù)。這種遍歷的方式和我們之前講過(guò)的都不太一樣。
需要借用一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)即隊(duì)列來(lái)實(shí)現(xiàn)，隊(duì)列先進(jìn)先出，符合一層一層遍歷的邏輯，而用棧先進(jìn)后出適合模擬深度優(yōu)先遍歷也就是遞歸的邏輯。
而這種層序遍歷方式就是圖論中的廣度優(yōu)先遍歷，只不過(guò)我們應(yīng)用在二叉樹(shù)上。
acm模式代碼
#include <iostream>
#include <vector>
#include <queue>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
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:
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::queue<TreeNode*> que;
std::vector<std::vector<int>> result;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int size = que.size();
std::vector<int> vec;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
vec.push_back(node->val);
que.pop();
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
int main() {
// 創(chuàng)建一個(gè)簡(jiǎn)單的二叉樹(shù)
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
Solution sol;
std::vector<std::vector<int>> level_order = sol.levelOrder(root);
// 打印層序遍歷結(jié)果
std::cout << "層序遍歷：" << std::endl;
for (const auto& level : level_order) {
for (int val : level) {
std::cout << val << " ";
}
std::cout << std::endl;
}
}
226 翻轉(zhuǎn)二叉樹(shù)
給你一棵二叉樹(shù)的根節(jié)點(diǎn) root ，翻轉(zhuǎn)這棵二叉樹(shù)，并返回其根節(jié)點(diǎn)。
示例 1：
輸入：root = [4,2,7,1,3,6,9]
輸出：[4,7,2,9,6,3,1]
示例 2：
輸入：root = [2,1,3]
輸出：[2,3,1]
示例 3：
輸入：root = []
輸出：[]
提示：
樹(shù)中節(jié)點(diǎn)數(shù)目范圍在 [0, 100] 內(nèi)
-100 <= Node.val <= 100
題目分析
確定遞歸函數(shù)的參數(shù)和返回值
參數(shù)就是要傳入節(jié)點(diǎn)的指針，不需要其他參數(shù)了，通常此時(shí)定下來(lái)主要參數(shù)，如果在寫遞歸的邏輯中發(fā)現(xiàn)還需要其他參數(shù)的時(shí)候，隨時(shí)補(bǔ)充。
返回值的話其實(shí)也不需要，但是題目中給出的要返回root節(jié)點(diǎn)的指針，可以直接使用題目定義好的函數(shù)，所以就函數(shù)的返回類型為TreeNode*。
TreeNode* invertTree(TreeNode* root)
確定終止條件
當(dāng)前節(jié)點(diǎn)為空的時(shí)候，就返回
if (root == NULL) return root;
確定單層遞歸的邏輯
因?yàn)槭窍惹靶虮闅v，所以先進(jìn)行交換左右孩子節(jié)點(diǎn)，然后反轉(zhuǎn)左子樹(shù)，反轉(zhuǎn)右子樹(shù)。
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
acm模式代碼
#include <iostream>
#include <algorithm>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
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:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
if (root == nullptr) {return root;}
}
std::swap(root->left,root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
void printTree(TreeNode* root) {
if (root != nullptr) {
std::cout << root->val << " ";
printTree(root->left);
printTree(root->right);
}
}
int main() {
// 創(chuàng)建一個(gè)簡(jiǎn)單的二叉樹(shù)
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
std::cout << "Original tree: ";
printTree(root);
std::cout << std::endl;
Solution sol;
root = sol.invertTree(root);
std::cout << "Inverted tree: ";
printTree(root);
std::cout << std::endl;
// 清理分配的內(nèi)存
delete root->left->left;
delete root->left->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
101 對(duì)稱二叉樹(shù)
題目分析
給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root ， 檢查它是否軸對(duì)稱。
示例 1：
輸入：root = [1,2,2,3,4,4,3]
輸出：true
示例 2：
輸入：root = [1,2,2,null,3,null,3]
輸出：false
提示：
樹(shù)中節(jié)點(diǎn)數(shù)目在范圍 [1, 1000] 內(nèi)
-100 <= Node.val <= 100
進(jìn)階：你可以運(yùn)用遞歸和迭代兩種方法解決這個(gè)問(wèn)題嗎？
題目分析
首先想清楚，判斷對(duì)稱二叉樹(shù)要比較的是哪兩個(gè)節(jié)點(diǎn)，要比較的可不是左右節(jié)點(diǎn)！
對(duì)于二叉樹(shù)是否對(duì)稱，要比較的是根節(jié)點(diǎn)的左子樹(shù)與右子樹(shù)是不是相互翻轉(zhuǎn)的，理解這一點(diǎn)就知道了其實(shí)我們要比較的是兩個(gè)樹(shù)（這兩個(gè)樹(shù)是根節(jié)點(diǎn)的左右子樹(shù)），所以在遞歸遍歷的過(guò)程中，也是要同時(shí)遍歷兩棵樹(shù)。
本題遍歷只能是“后序遍歷”，因?yàn)槲覀円ㄟ^(guò)遞歸函數(shù)的返回值來(lái)判斷兩個(gè)子樹(shù)的內(nèi)側(cè)節(jié)點(diǎn)和外側(cè)節(jié)點(diǎn)是否相等。
正是因?yàn)橐闅v兩棵樹(shù)而且要比較內(nèi)側(cè)和外側(cè)節(jié)點(diǎn)，所以準(zhǔn)確的來(lái)說(shuō)是一個(gè)樹(shù)的遍歷順序是左右中，一個(gè)樹(shù)的遍歷順序是右左中。
但都可以理解算是后序遍歷，盡管已經(jīng)不是嚴(yán)格上在一個(gè)樹(shù)上進(jìn)行遍歷的后序遍歷了。
其實(shí)后序也可以理解為是一種回溯，當(dāng)然這是題外話，講回溯的時(shí)候會(huì)重點(diǎn)講的
遞歸法
遞歸三部曲
確定遞歸函數(shù)的參數(shù)和返回值
因?yàn)槲覀円容^的是根節(jié)點(diǎn)的兩個(gè)子樹(shù)是否是相互翻轉(zhuǎn)的，進(jìn)而判斷這個(gè)樹(shù)是不是對(duì)稱樹(shù)，所以要比較的是兩個(gè)樹(shù)，參數(shù)自然也是左子樹(shù)節(jié)點(diǎn)和右子樹(shù)節(jié)點(diǎn)。
返回值自然是bool類型。
bool compare(TreeNode* left, TreeNode* right)
確定終止條件
要比較兩個(gè)節(jié)點(diǎn)數(shù)值相不相同，首先要把兩個(gè)節(jié)點(diǎn)為空的情況弄清楚！否則后面比較數(shù)值的時(shí)候就會(huì)操作空指針了。
節(jié)點(diǎn)為空的情況有：（注意我們比較的其實(shí)不是左孩子和右孩子，所以如下我稱之為左節(jié)點(diǎn)右節(jié)點(diǎn)）
左節(jié)點(diǎn)為空，右節(jié)點(diǎn)不為空，不對(duì)稱，return false
左不為空，右為空，不對(duì)稱 return false
左右都為空，對(duì)稱，返回true
此時(shí)已經(jīng)排除掉了節(jié)點(diǎn)為空的情況，那么剩下的就是左右節(jié)點(diǎn)不為空：
左右都不為空，比較節(jié)點(diǎn)數(shù)值，不相同就return false
此時(shí)左右節(jié)點(diǎn)不為空，且數(shù)值也不相同的情況我們也處理了。
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false; // 注意這里我沒(méi)有使用else
確定單層遞歸的邏輯
此時(shí)才進(jìn)入單層遞歸的邏輯，單層遞歸的邏輯就是處理 左右節(jié)點(diǎn)都不為空，且數(shù)值相同的情況。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-800084.html
比較二叉樹(shù)外側(cè)是否對(duì)稱：傳入的是左節(jié)點(diǎn)的左孩子，右節(jié)點(diǎn)的右孩子。
比較內(nèi)側(cè)是否對(duì)稱，傳入左節(jié)點(diǎn)的右孩子，右節(jié)點(diǎn)的左孩子。
如果左右都對(duì)稱就返回true ，有一側(cè)不對(duì)稱就返回false 。
代碼如下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-800084.html
bool outside = compare(left->left, right->right); // 左子樹(shù)：左、 右子樹(shù)：右
bool inside = compare(left->right, right->left); // 左子樹(shù)：右、 右子樹(shù)：左
bool isSame = outside && inside; // 左子樹(shù)：中、 右子樹(shù)：中（邏輯處理）
return isSame;
acm 完整代碼
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
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:
bool compare(TreeNode* left, TreeNode* right) {
if (left == nullptr && right != nullptr) return false;
else if (left != nullptr && right == nullptr) return false;
else if (left == nullptr && right == nullptr) return true;
else if (left->val != right->val) return false;
bool outside = compare(left->left, right->right);
bool inside = compare(left->right, right->left);
bool isSame = outside && inside;
return isSame;
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return compare(root->left, root->right);
}
};
int main() {
// 創(chuàng)建一個(gè)簡(jiǎn)單的對(duì)稱二叉樹(shù)
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(2);
root->left->left = new TreeNode(3);
root->left->right = new TreeNode(4);
root->right->left = new TreeNode(4);
root->right->right = new TreeNode(3);
Solution sol;
bool result = sol.isSymmetric(root);
std::cout << "Is the tree symmetric? " << (result ? "Yes" : "No") << std::endl;
// 清理分配的內(nèi)存
delete root->left->left;
delete root->left->right;
delete root->left;
delete root->right->left;
delete root->right->right;
delete root->right;
delete root;
return 0;
}
到了這里，關(guān)于算法訓(xùn)練day15Leetcode102二叉樹(shù)層序遍歷226翻轉(zhuǎn)二叉樹(shù)101對(duì)稱二叉樹(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
