leetcode第一刷_Recover Binary Search Tree
這是一道好題，思路盡管有，可是提交之后總是有數(shù)據(jù)過不了，又依照數(shù)據(jù)改改改。最后代碼都沒法看了。收到的教訓(xùn)是假設(shè)必須為自己的代碼加上非常多非常多特殊的限定。來過一些特殊的數(shù)據(jù)的話。說明代碼本身有非常大的漏洞。
這道題，我想到了要用兩個指針保存亂序的節(jié)點，甚至想到了用一個pre指針來保存前面一個節(jié)點，可是問題出在哪里呢？我認(rèn)為應(yīng)該是自己對樹的遍歷理解的不夠深刻。既然知道了二叉搜索樹一定是用中序遍歷的，那么程序的框架應(yīng)該立即寫的出來，先左子樹，再根，再右子樹，那你說什么時候更新pre指針呢，當(dāng)然是訪問根節(jié)點的時候。假設(shè)把每次返回的節(jié)點作為接下來考慮的左子樹，事實上并非一種中序遍歷，更像是前序遍歷。另一點，我當(dāng)時總是想單獨的找出這兩個亂序的節(jié)點，然后加了非常多特殊情況考慮假設(shè)他們兩個相鄰怎么辦。事實上這不是非常好解決的嗎，由于一共僅僅有兩個節(jié)點亂掉了，那么一開始不滿足條件的那對節(jié)點肯定包括了當(dāng)中一個，并且是較大的那個是亂掉的。往后的話，假設(shè)又出現(xiàn)了這個問題，一定是較小那個，不用加不論什么特殊情況的考慮。
代碼很簡潔，好羞愧：
TreeNode *e1, *e2, *pre;
void inorder(TreeNode *root){if(root == NULL) return;if(root->left)inorder(root->left);if(pre&&pre->val>root->val){if(e1 == NULL) e1 = pre, e2 = root;else e2 = root;}pre = root;if(root->right)inorder(root->right);return;
} class Solution {
public:void recoverTree(TreeNode *root) {pre = NULL, e1 = NULL, e2 = NULL;inorder(root);swap(e1->val, e2->val);return;}
};轉(zhuǎn)載于:https://www.cnblogs.com/jzdwajue/p/6781985.html
總結(jié)
以上是生活随笔為你收集整理的leetcode第一刷_Recover Binary Search Tree的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
