做這題的時候發現其實上一題的做法是錯誤的，BST的中序排序是一個上升序列，所以判斷的時候只需要按中序排序， 然后判斷是不是上升的就ok！所以98也是這樣做的！！！ 至于這題，為什么n1 和 n2 記錄的不一樣呢？ N1 是記錄PRe的而n2是記錄root的 因為你在紙上寫一個上升序列，然后換磚兩個數，你就會發現原因！！！
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: int num; TreeNode* n1; TreeNode* n2; TreeNode* pre = new TreeNode(INT_MIN); //int pre; void change(TreeNode* root){ if(root == NULL) return ; change(root -> left); if(num == 0 && pre -> val >= root -> val){ num ++; n1 = pre; } if(num != 0 && pre -> val >= root -> val) n2 = root; pre = root; change(root -> right); } void recoverTree(TreeNode* root) { if(root == NULL) return ; num = 0; change(root); int t; t = n1 -> val; n1 -> val = n2 -> val; n2 -> val = t; }};新聞熱點
疑難解答
