Recover Binary Search Tree [leetcode]
来源：程序员人生 发布时间：2014-10-02 08:00:01 阅读次数：2229次
本题是在中序遍历的基础上，找不合规范（不是递增）的树节点对，然后交换
首先看两种序列：
1. 1 3 2 4=>应该交换3和2
2. 4 3 2 1=>应交换4和1
这两种序列对应了不符合条件的BST的中序遍历序列的所有可能性---两个节点中序遍历相邻/不相邻
如果我们用一个数组swap保存所有中序遍历不递增的结果，那么这个数组只可能是2或者4的大小
而我们交换数组中节点对内容，只需交换第一个和最后一个树节点对的内容
vector<TreeNode *> swap;
TreeNode * pre;
void recoverTree(TreeNode *root)
{
pre = new TreeNode(-999999);
swap = vector<TreeNode *>();
inorder(root);
if (swap.size() > 1)
{
int val = swap[0]->val;
swap[0]->val = swap[swap.size() - 1]->val;
swap[swap.size() - 1]->val = val;
}
}
void inorder(TreeNode * root)
{
if (root == NULL) return;
inorder(root->left);
if (pre->val > root->val)
{
swap.push_back(pre);
swap.push_back(root);
}
pre = root;
inorder(root->right);
}
由于只交换第一个和最后一个树节点内容，我们可以只保存第一个和最后一个Node
if(!first) first = pre;
last = root;
替换
swap.push_back(pre); swap.push_back(root);
代码如下：
TreeNode * first, * last;
TreeNode * pre;
void recoverTree(TreeNode *root)
{
pre = new TreeNode(-999999);
first = last = NULL;
inorder(root);
if (first)
{
int val = first->val;
first->val = last->val;
last->val = val;
}
}
void inorder(TreeNode * root)
{
if (root == NULL) return;
inorder(root->left);
if (pre->val > root->val)
{
if (!first) first = pre;
last = root;
}
pre = root;
inorder(root->right);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
