建站
咨詢
售后
建站咨詢
新聞中心
今天小編給大家分享一下C++怎么復(fù)原二叉搜索樹的相關(guān)知識點(diǎn)，內(nèi)容詳細(xì)，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。
創(chuàng)新互聯(lián)建站基于分布式IDC數(shù)據(jù)中心構(gòu)建的平臺為眾多戶提供成都棕樹機(jī)房 四川大帶寬租用 成都機(jī)柜租用 成都服務(wù)器租用。
復(fù)原二叉搜索樹
Example 1:
Input: [1,3,null,null,2]
1
/
3
2Output: [3,1,null,null,2]
3
/
1
2
Example 2:
Input: [3,1,4,null,null,2]
3
/
1 4
/
2Output: [2,1,4,null,null,3]
2
/
1 4
/
3
Follow up:
A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?
這道題要求我們復(fù)原一個二叉搜索樹，說是其中有兩個的順序被調(diào)換了，題目要求上說 O(n) 的解法很直觀，這種解法需要用到遞歸，用中序遍歷樹，并將所有節(jié)點(diǎn)存到一個一維向量中，把所有節(jié)點(diǎn)值存到另一個一維向量中，然后對存節(jié)點(diǎn)值的一維向量排序，在將排好的數(shù)組按順序賦給節(jié)點(diǎn)。這種最一般的解法可針對任意個數(shù)目的節(jié)點(diǎn)錯亂的情況，這里先貼上此種解法：
解法一：
// O(n) space complexity
class Solution {
public:
void recoverTree(TreeNode* root) {
vector list;
vector vals;
inorder(root, list, vals);
sort(vals.begin(), vals.end());
for (int i = 0; i < list.size(); ++i) {
list[i]->val = vals[i];
}
}
void inorder(TreeNode* root, vector& list, vector& vals) {
if (!root) return;
inorder(root->left, list, vals);
list.push_back(root);
vals.push_back(root->val);
inorder(root->right, list, vals);
}
}; 然后博主上網(wǎng)搜了許多其他解法，看到另一種是用雙指針來代替一維向量的，但是這種方法用到了遞歸，也不是 O(1) 空間復(fù)雜度的解法，這里需要三個指針，first，second 分別表示第一個和第二個錯亂位置的節(jié)點(diǎn)，pre 指向當(dāng)前節(jié)點(diǎn)的中序遍歷的前一個節(jié)點(diǎn)。這里用傳統(tǒng)的中序遍歷遞歸來做，不過在應(yīng)該輸出節(jié)點(diǎn)值的地方，換成了判斷 pre 和當(dāng)前節(jié)點(diǎn)值的大小，如果 pre 的大，若 first 為空，則將 first 指向 pre 指的節(jié)點(diǎn)，把 second 指向當(dāng)前節(jié)點(diǎn)。這樣中序遍歷完整個樹，若 first 和 second 都存在，則交換它們的節(jié)點(diǎn)值即可。這個算法的空間復(fù)雜度仍為 O(n)，n為樹的高度，參見代碼如下：
解法二：
// Still O(n) space complexity
class Solution {
public:
TreeNode *pre = NULL, *first = NULL, *second = NULL;
void recoverTree(TreeNode* root) {
inorder(root);
swap(first->val, second->val);
}
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
if (!pre) pre = root;
else {
if (pre->val > root->val) {
if (!first) first = pre;
second = root;
}
pre = root;
}
inorder(root->right);
}
};我們其實(shí)也可以使用迭代的寫法，因?yàn)橹行虮闅v Binary Tree Inorder Traversal 也可以借助棧來實(shí)現(xiàn)，原理還是跟前面的相同，記錄前一個結(jié)點(diǎn)，并和當(dāng)前結(jié)點(diǎn)相比，如果前一個結(jié)點(diǎn)值大，那么更新 first 和 second，最后交換 first 和 second 的結(jié)點(diǎn)值即可，參見代碼如下：
解法三：
// Always O(n) space complexity
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *pre = NULL, *first = NULL, *second = NULL, *p = root;
stack st;
while (p || !st.empty()) {
while (p) {
st.push(p);
p = p->left;
}
p = st.top(); st.pop();
if (pre) {
if (pre->val > p->val) {
if (!first) first = pre;
second = p;
}
}
pre = p;
p = p->right;
}
swap(first->val, second->val);
}
}; 這道題的真正符合要求的解法應(yīng)該用的 Morris 遍歷，這是一種非遞歸且不使用棧，空間復(fù)雜度為 O(1) 的遍歷方法，可參見博主之前的博客 Binary Tree Inorder Traversal，在其基礎(chǔ)上做些修改，加入 first, second 和 parent 指針，來比較當(dāng)前節(jié)點(diǎn)值和中序遍歷的前一節(jié)點(diǎn)值的大小，跟上面遞歸算法的思路相似，代碼如下：
解法四：
// Now O(1) space complexity
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *first = nullptr, *second = nullptr, *cur = root, *pre = nullptr ;
while (cur) {
if (cur->left){
TreeNode *p = cur->left;
while (p->right && p->right != cur) p = p->right;
if (!p->right) {
p->right = cur;
cur = cur->left;
continue;
} else {
p->right = NULL;
}
}
if (pre && cur->val < pre->val){
if (!first) first = pre;
second = cur;
}
pre = cur;
cur = cur->right;
}
swap(first->val, second->val);
}
};以上就是“C++怎么復(fù)原二叉搜索樹”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
網(wǎng)站標(biāo)題：C++怎么復(fù)原二叉搜索樹
鏈接URL：http://www.ef60e0e.cn/article/jodgjd.html
