99. Recover Binary Search Tree

2019-11-10 21:47:46

字体：大中小

来源：转载

供稿：网友

做这题的时候发现其实上一题的做法是错误的，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; }};

上一篇：resultMap和resultType引起的错误

下一篇：cf 766 d Mahmoud and a Dictionary（带权并查集）