摘要
- 從序列構(gòu)造二叉樹(shù)的關(guān)鍵是要找到劃分點(diǎn)酌呆，將序列分為左子樹(shù)的序列和右子樹(shù)的序列
- 在對(duì)二叉樹(shù)進(jìn)行訪問(wèn)前，要根據(jù)問(wèn)題確定用哪種遍歷方式進(jìn)行訪問(wèn)
- 二叉搜索樹(shù)的定義是左子樹(shù)的所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值搔耕，右子樹(shù)的所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值隙袁；是“左子樹(shù)”和“右子樹(shù)”，而不是“左孩子”和右孩子
LeetCode654 最大二叉樹(shù)
- 初見(jiàn)題目的想法弃榨，這道題與用中序序列和后序序列構(gòu)造二叉樹(shù)有異曲同工之妙菩收，只是找劃分節(jié)點(diǎn)的規(guī)則不同：
- 用中序序列和后序序列構(gòu)造二叉樹(shù)，是將后序序列的最后一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)鲸睛，然后找到根節(jié)點(diǎn)在中序序列中的位置娜饵，將中序序列劃分為左子樹(shù)的序列和右子樹(shù)的序列，再通過(guò)左官辈、右子樹(shù)的序列長(zhǎng)度箱舞，在后序序列中劃分出左子樹(shù)的序列和右子樹(shù)的序列。上述過(guò)程是遞歸的拳亿。
- 而本題定義的最大二叉樹(shù)晴股，找劃分節(jié)點(diǎn)的規(guī)則變?yōu)榱苏倚蛄兄兄底畲蟮墓?jié)點(diǎn)作為根節(jié)點(diǎn)，然后將序列劃分為左子樹(shù)的序列和右子樹(shù)的序列风瘦，這個(gè)過(guò)程也是遞歸的队魏。
- 明確了劃分序列的過(guò)程胡桨，接下來(lái)就是寫(xiě)遞歸函數(shù)：
- 傳入的參數(shù)和返回值：傳入構(gòu)造二叉樹(shù)的序列，以及當(dāng)前子樹(shù)對(duì)應(yīng)的區(qū)間的左邊界和右邊界涌哲，本題采用左閉右開(kāi)區(qū)間狗唉。返回值為當(dāng)前子樹(shù)的根節(jié)點(diǎn)肾筐。
- 遞歸的終止條件：序列內(nèi)沒(méi)有節(jié)點(diǎn)，或序列內(nèi)僅有一個(gè)節(jié)點(diǎn)（說(shuō)明到達(dá)葉節(jié)點(diǎn)）
- 單層遞歸的邏輯：首先找到序列內(nèi)值最大的節(jié)點(diǎn)，記錄該節(jié)點(diǎn)在序列中的位置，并將其作為根節(jié)點(diǎn)；然后，以根節(jié)點(diǎn)為分界，將序列劃分為左子樹(shù)的序列和右子樹(shù)的序列，嘗試構(gòu)造根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。
完整的題解代碼如下
class Solution {
public:
TreeNode* construct(vector<int>& nums, int l, int r) {// [l, r)
if (l >= r) return nullptr;
if (r - l == 1) return new TreeNode(nums[l]);
int maxVal = INT_MIN;
int delim = 0;
for (int i = l; i < r; i++) {
if (nums[i] > maxVal) {
maxVal = nums[i];
delim = i;
}
}
TreeNode* cur = new TreeNode(nums[delim]);
cur->left = construct(nums, l, delim);
cur->right = construct(nums, delim + 1, r);
return cur;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return construct(nums, 0, nums.size());
}
};
LeetCode617 合并二叉樹(shù)
- 初見(jiàn)題目的想法：這道題乍一看涉及同時(shí)訪問(wèn)兩棵二叉樹(shù)瘸恼，但實(shí)際上同時(shí)訪問(wèn)的兩棵二叉樹(shù)的節(jié)點(diǎn)位置是相同的，所以邏輯上和訪問(wèn)一棵二叉樹(shù)類(lèi)似。
- 采用前序遍歷來(lái)合并二叉樹(shù)
- 傳入的參數(shù)和返回值：傳入兩棵樹(shù)位置”重疊的“節(jié)點(diǎn)焚刚，返回合并后的節(jié)點(diǎn)
- 遞歸的終止條件：兩棵樹(shù)在該位置的節(jié)點(diǎn)都為空
- 單層遞歸的的邏輯：首先合并當(dāng)前位置的兩個(gè)”重疊的”節(jié)點(diǎn)碳柱，然后嘗試合并當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)莲镣。
完整題解代碼如下福稳，
class Solution {
public:
TreeNode* merge(TreeNode* cur1, TreeNode* cur2) {
if (!cur1 && !cur2) return nullptr;
if (cur1 && !cur2) return cur1;
if (!cur1 && cur2) return cur2;
TreeNode* mergedNode = new TreeNode(cur1->val + cur2->val);
mergedNode->left = merge(cur1->left, cur2->left);
mergedNode->right = merge(cur1->right, cur2->right);
return mergedNode;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return merge(root1, root2);
}
};
需要注意的是，上面的題解代碼還是沒(méi)有完全構(gòu)造一棵新的二叉樹(shù)瑞侮，直接return cur1或return cur2會(huì)讓新的二叉樹(shù)與舊的二叉樹(shù)共享一些節(jié)點(diǎn)的圆，所以可以做以下修改
class Solution {
public:
TreeNode* merge(TreeNode* cur1, TreeNode* cur2) {
if (!cur1 && !cur2) return nullptr;
if (cur1 && !cur2) return new TreeNode(cur1->val, cur1->left, cur1->right);
if (!cur1 && cur2) return new TreeNode(cur2->val, cur2->left, cur2->right);
TreeNode* mergedNode = new TreeNode(cur1->val + cur2->val);
mergedNode->left = merge(cur1->left, cur2->left);
mergedNode->right = merge(cur1->right, cur2->right);
return mergedNode;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return merge(root1, root2);
}
};
LeetCode700 二叉搜索樹(shù)中的搜索
- 二叉搜索樹(shù)中的搜索非常直觀，和二分搜索很相似：
- 若目標(biāo)值比當(dāng)前節(jié)點(diǎn)的值小半火，則去訪問(wèn)當(dāng)前節(jié)點(diǎn)的左孩子越妈；若目標(biāo)值比當(dāng)前節(jié)點(diǎn)的值大，則去訪問(wèn)當(dāng)前節(jié)點(diǎn)的右孩子钮糖。
- 從根節(jié)點(diǎn)開(kāi)始梅掠，重復(fù)上述步驟，直到找到目標(biāo)值店归，或當(dāng)前節(jié)點(diǎn)為空節(jié)點(diǎn)阎抒。
遞歸法
class Solution {
public:
TreeNode* search(TreeNode* cur, int& val) {
TreeNode* res = nullptr;
// 短路判斷，cur為空則直接返回消痛，不會(huì)再判斷cur->val == val挠蛉，避免操作空指針
if (!cur || cur->val == val) return cur;
if (val < cur->val) res = search(cur->left, val);
if (val > cur->val) res = search(cur->right, val);
return res;
}
TreeNode* searchBST(TreeNode* root, int val) {
return search(root, val);
}
};
迭代法
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* cur = root;
while (cur) {
if (val < cur->val) cur = cur->left;
else if (val > cur->val) cur = cur->right;
else return cur;
}
return cur;
}
};
LeetCode98 驗(yàn)證二叉搜索樹(shù)
- 初見(jiàn)題目的想法，陷入了經(jīng)典誤區(qū)
class Solution {
public:
bool isValid(TreeNode* cur) {
if (cur->left && cur->right) {
if (cur->left->val >= cur->val || cur->right->val <= cur->val) return false;
else return isValid(cur->left) && isValid(cur->right);
}
if (cur->left && !cur->right) {
if (cur->left->val >= cur->val) return false;
return isValid(cur->left);
}
if (!cur->left && cur->right) {
if (cur->right->val <= cur->val) return false;
return isValid(cur->right);
}
return true;
}
bool isValidBST(TreeNode* root) {
if (!root) return true;
else return isValid(root);
}
};
- 為什么會(huì)錯(cuò)肄满？這段代碼的邏輯只能保證“左孩子的值小于父節(jié)點(diǎn)的值和右孩子的值大于父節(jié)點(diǎn)的值”谴古，這只是局部的质涛。而二叉搜索樹(shù)要求的是“左子樹(shù)所有節(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值和右子樹(shù)所有節(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值。所以上面這段代碼乍一看沒(méi)什么問(wèn)題掰担，但是它是不符合二叉查找樹(shù)的定義的汇陆。
- 下圖就是反例。對(duì)于每個(gè)節(jié)點(diǎn)带饱，其左孩子的都值都小于自己的值毡代，右孩子的值都大于自己的值，但是這并不能保證左子樹(shù)和右子樹(shù)也符合要求勺疼。下圖的 節(jié)點(diǎn)3 就是問(wèn)題所在教寂，3 小于 6 沒(méi)錯(cuò)，但是 3 也小于 5执庐，3 實(shí)際上應(yīng)該在 5 的左子樹(shù)酪耕。下圖所示的二叉樹(shù)并不是一棵二叉查找樹(shù)。
這不是二叉搜索樹(shù)
- 再回顧一次二叉搜索樹(shù)的定義轨淌，我開(kāi)始思考應(yīng)該用什么樣的遍歷方式更加合適
- 二叉搜索樹(shù)是一個(gè)有序樹(shù)：
- 若它的左子樹(shù)不空迂烁，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
- 若它的右子樹(shù)不空递鹉，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值盟步；
- 它的左、右子樹(shù)也分別為二叉搜索樹(shù)
- 二叉搜索樹(shù)的定義躏结，使得二叉搜索樹(shù)的中序遍歷序列一定是一個(gè)升序序列却盘。
- 二叉搜索樹(shù)是一個(gè)有序樹(shù)：
- 所以，只要在中序遍歷的過(guò)程中媳拴，驗(yàn)證當(dāng)前節(jié)點(diǎn)的值是否比中序遍歷中上一個(gè)節(jié)點(diǎn)的值大即可
- 傳入的參數(shù)和返回值：傳入當(dāng)前節(jié)點(diǎn)和上一個(gè)節(jié)點(diǎn)谷炸。返回當(dāng)前子樹(shù)是否為二叉搜索樹(shù)。
-
遞歸的終止條件：當(dāng)前節(jié)點(diǎn)為空禀挫，空樹(shù)是一棵二叉搜索樹(shù)旬陡，直接返回
true；或者可以理解為空節(jié)點(diǎn)對(duì)是否是二叉搜索樹(shù)沒(méi)有影響语婴，可以直接返回true描孟。 - 單層遞歸的處理邏輯：要注意是中序遍歷，所以先判斷左子樹(shù)是否是二叉搜索樹(shù)砰左，再判斷當(dāng)前節(jié)點(diǎn)的值是否大于上一個(gè)節(jié)點(diǎn)的值匿醒，然后再去判斷右子樹(shù)是否為二叉搜索樹(shù)。
完整題解代碼如下
class Solution {
public:
bool isValid(TreeNode* cur, TreeNode*& pre) {
if (!cur) return true;
bool left = isValid(cur->left, pre);
if (pre && pre->val >= cur->val) return false;
pre = cur;
bool right = isValid(cur->right, pre);
return left && right;
}
bool isValidBST(TreeNode* root) {
TreeNode* pre = nullptr;
return isValid(root, pre);
}
};
