一天一道LeetCode
本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处
(一)题目
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
(二)解题
题目大意:一个二叉搜索树,交换了其中的两个节点,请找出它们并恢复成二叉搜索树。
解题思路:二叉搜索树的特征是中序遍历是按序排列的,如果交换了其中的两个节点,那么必然有不满足升序的点,所有采用中序遍历,每次记录该节点的先驱节点,比较大小,如果大于该节点的值,则为错误节点。找出两个后交换过来即可。
详细解释见代码注释
/**
* 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:
void recoverTree(TreeNode* root) {
vector<TreeNode*> mistake(2,NULL);//用来存储两个错误的节点
TreeNode* pre = NULL;
dfsTree(root,pre,mistake);
int vt = mistake[0]->val;.//交换两个节点的值
mistake[0]->val=mistake[1]->val;
mistake[1]->val = vt;
}
void dfsTree(TreeNode* root,TreeNode* &pre,vector<TreeNode*>& mistake)
{
if(root==NULL) return;
dfsTree(root->left,pre,mistake);//一直往左子树搜索
if(pre!=NULL&&pre->val>root->val)//如果先驱节点存在,且大于当前节点,则判定为错误节点
{
if(mistake[0]==NULL) mistake[0] = pre;.//记录第一个错误节点
mistake[1] = root;//第二个错误节点必为当前节点
}
pre = root;//记录先驱节点
dfsTree(root->right,pre,mistake);//一直往右子树搜索
}
};