recover-binary-search-tree

题目描述

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?

意思就是一个二叉排序树中的两个元素互换了位置,我们需要将其调整过来。

解题思路

根据BST(二叉排序树)中序遍历结果为增序的特点,在中序遍历该二叉树的过程中找到两处不符合BST特点的位置并加以保存,之后将两者交换位置。

源代码表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
TreeNode *pre=NULL; //当前访问结点的前一个结点
TreeNode *first=NULL; //第一个需要调换的结点
TreeNode *second=NULL; //第二个需要调换的结点
public:
//利用中序遍历思想找出两个位置错误的结点
void Inorder(TreeNode *root) {
if (root==nullptr)
return; //递归结束条件
Inorder(root->left);
if(pre!=NULL&&pre->val>root->val) {
//不满足BST特性,说明pre结点位置有误
if(first==NULL)
first=pre;
//如果此时的root即为第二个错误的结点位置,那么这一次就找到了两个结点位置,
//如果不是的话,second在后面的执行的过程中会被重新赋值
second=root;
}
pre=root; //每次判断之后将pre向前推进
Inorder(root->right);
}
void recoverTree(TreeNode *root) {
if (!root)
return ;
Inorder(root);
int tmp=first->val;
first->val=second->val;
second->val=tmp; //将找到的两个错误结点互换位置
}
};

原理分析

之前对于递归调用总是有些迷糊,在上一篇博客中,我分析了一下先序递归遍历二叉树的流程,对于这道题也是有一定的帮助,我稍微加以改进即能够将这道题递归调用的流程分析出来,我觉得这种用大括号来表示层层递归的方式还是挺不错的,容易理解。

例如,给定一棵如下结构的二叉排序树


从中可以看出,结点7和结点2的位置有错误,按照上述代码执行的话,其中Inorder函数的具体流程如下:


从图中可以看出,当Inorder函数执行结束后,first=7,second=2,正是我们需要找的结点,将它们进行互换即可。

-------------The End-------------