發(fā)現(xiàn)更多計(jì)算機(jī)知識(shí)，歡迎訪問(wèn)Cr不是鉻的個(gè)人網(wǎng)站

最近數(shù)據(jù)結(jié)構(gòu)學(xué)到二叉樹(shù)，就刷了刷力扣，寫(xiě)這篇文章也是輔助記憶。

103二叉樹(shù)鋸齒形遍歷

---

要解出本道題，首先要會(huì)層次遍歷。層次遍歷我們都知道用一個(gè)隊(duì)列去實(shí)現(xiàn)就行。但是力扣這里的輸出時(shí)一個(gè)二維的vector，每一層的值在不同的列表里面。這里是一個(gè)難點(diǎn)。這個(gè)鋸齒形遍歷無(wú)非加一個(gè)判斷本層是奇數(shù)還是偶數(shù)層，然后用內(nèi)置的revers函數(shù)處理一下就可。

代碼:

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret; // 存儲(chǔ)結(jié)果的二維向量queue<TreeNode*> dq; // 輔助隊(duì)列用于層序遍歷if (root == nullptr) {return ret; // 如果根節(jié)點(diǎn)為空，直接返回空結(jié)果}dq.push(root); // 將根節(jié)點(diǎn)入隊(duì)int level = 1; // 層級(jí)標(biāo)志，初始為1while (!dq.empty()) {int size = dq.size(); // 當(dāng)前層的節(jié)點(diǎn)數(shù)vector<int> tmp; // 臨時(shí)向量存儲(chǔ)當(dāng)前層的節(jié)點(diǎn)值for (int i = 0; i < size; i++) {TreeNode* node = dq.front(); // 取出隊(duì)首節(jié)點(diǎn)dq.pop(); // 出隊(duì)tmp.push_back(node->val); // 將節(jié)點(diǎn)值存入臨時(shí)向量if (node->left != nullptr) {dq.push(node->left); // 左子節(jié)點(diǎn)入隊(duì)}if (node->right != nullptr) {dq.push(node->right); // 右子節(jié)點(diǎn)入隊(duì)}}if (level % 2 == 0) {reverse(tmp.begin(), tmp.end()); // 如果是偶數(shù)層級(jí)，將臨時(shí)向量反轉(zhuǎn)}ret.push_back(tmp); // 將當(dāng)前層的節(jié)點(diǎn)值向量存入結(jié)果向量level++; // 層級(jí)標(biāo)志自增}return ret; // 返回結(jié)果向量}
};

103對(duì)稱二叉樹(shù)

判斷對(duì)稱二叉樹(shù)可以在判斷完全相同的二叉樹(shù)的基礎(chǔ)上面進(jìn)行。只是遞歸的時(shí)候變成了left->right ,rigth->left這種.

利用遞歸解決代碼:

class Solution {
public:// 判斷兩個(gè)節(jié)點(diǎn)是否鏡像對(duì)稱bool isMirror(TreeNode* left, TreeNode* right) {if (left == nullptr && right == nullptr) {return true; // 如果兩個(gè)節(jié)點(diǎn)都為空，則它們鏡像對(duì)稱} else if (left == nullptr || right == nullptr) {return false; // 如果其中一個(gè)節(jié)點(diǎn)為空，則它們不鏡像對(duì)稱} else {// 判斷當(dāng)前節(jié)點(diǎn)的值相等，并且左子樹(shù)的左子節(jié)點(diǎn)與右子樹(shù)的右子節(jié)點(diǎn)鏡像對(duì)稱，// 左子樹(shù)的右子節(jié)點(diǎn)與右子樹(shù)的左子節(jié)點(diǎn)鏡像對(duì)稱return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left);}}// 判斷二叉樹(shù)是否對(duì)稱bool isSymmetric(TreeNode* root) {if (root == nullptr) {return true; // 如果根節(jié)點(diǎn)為空，則認(rèn)為是對(duì)稱的}return isMirror(root->left, root->right); // 判斷根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)是否鏡像對(duì)稱}
};

在isMirror函數(shù)中，如果兩個(gè)節(jié)點(diǎn)都為空，則它們鏡像對(duì)稱；如果其中一個(gè)節(jié)點(diǎn)為空，則它們不鏡像對(duì)稱；否則，判斷當(dāng)前節(jié)點(diǎn)的值相等，并且左子樹(shù)的左子節(jié)點(diǎn)與右子樹(shù)的右子節(jié)點(diǎn)鏡像對(duì)稱，左子樹(shù)的右子節(jié)點(diǎn)與右子樹(shù)的左子節(jié)點(diǎn)鏡像對(duì)稱

由前序遍歷與中序遍歷得到樹(shù)

這是一個(gè)非常經(jīng)典的問(wèn)題，這里我給出一個(gè)我覺(jué)得很容易理解的代碼:

class Solution {
public:// 通過(guò)前序遍歷和中序遍歷構(gòu)建二叉樹(shù)的遞歸函數(shù)TreeNode* build(vector<int>& preorder, int l1, int r1, vector<int>& inorder, int l2, int r2) {TreeNode* root = new TreeNode(preorder[l1]); // 創(chuàng)建當(dāng)前子樹(shù)的根節(jié)點(diǎn)int i = l2;while (inorder[i] != root->val) {i++; // 在中序遍歷中找到根節(jié)點(diǎn)的位置}int Llen = i - l2; // 計(jì)算左子樹(shù)的長(zhǎng)度int Rlen = r2 - i; // 計(jì)算右子樹(shù)的長(zhǎng)度if (Llen <= 0) {root->left = nullptr; // 如果左子樹(shù)長(zhǎng)度小于等于0，說(shuō)明左子樹(shù)為空} else {// 遞歸構(gòu)建左子樹(shù)，左子樹(shù)的前序遍歷范圍為[l1+1, l1+Llen]，中序遍歷范圍為[l2, i-1]root->left = build(preorder, l1 + 1, l1 + Llen, inorder, l2, i - 1);}if (Rlen <= 0) {root->right = nullptr; // 如果右子樹(shù)長(zhǎng)度小于等于0，說(shuō)明右子樹(shù)為空} else {// 遞歸構(gòu)建右子樹(shù)，右子樹(shù)的前序遍歷范圍為[l1+Llen+1, r1]，中序遍歷范圍為[i+1, r2]root->right = build(preorder, l1 + Llen + 1, r1, inorder, i + 1, r2);}return root; // 返回當(dāng)前子樹(shù)的根節(jié)點(diǎn)}// 構(gòu)建二叉樹(shù)TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size(); // 前序遍歷序列的長(zhǎng)度int m = inorder.size(); // 中序遍歷序列的長(zhǎng)度TreeNode* root;root = build(preorder, 0, n - 1, inorder, 0, m - 1); // 調(diào)用遞歸函數(shù)構(gòu)建二叉樹(shù)return root; // 返回根節(jié)點(diǎn)}
};

考慮一下，如果要求的是從后序遍歷和中序遍歷得到樹(shù)呢？上述代碼該如何變化呢？

這里也貼上代碼:

class Solution {
public:TreeNode* build(vector<int>& inorder, int l1, int r1, vector<int>& postorder, int l2, int r2){if (l1 > r1 || l2 > r2)return nullptr;TreeNode* root = new TreeNode(postorder[r2]);int i = l1;while (inorder[i] != root->val)i++;int Llen = i - l1;int Rlen = r1 - i;root->left = build(inorder, l1, i - 1, postorder, l2, l2 + Llen - 1);root->right = build(inorder, i + 1, r1, postorder, l2 + Llen, r2 - 1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n = inorder.size();int m = postorder.size();TreeNode* root;root = build(inorder, 0, n - 1, postorder, 0, m - 1);return root;}
};

本文由博客一文多發(fā)平臺(tái) OpenWrite 發(fā)布！