题目来源:https://leetcode.com/problems/increasing-order-search-tree/description/

标记难度:Easy

提交次数:3/6

代码效率:

  • 中序遍历(未优化):68ms
  • 中序遍历+额外空间:60ms
  • 优化的中序遍历:44ms

题意

给定一棵二叉树,要求把原来的树按照中序遍历的顺序重新组织,拉成一条长链,第一个结点在树根,下一个结点是它的右孩子,以此类推。

分析

这道题写了二十多分钟,错了三次,心态崩了。题目描述原来给的是一棵二叉搜索树,于是我就直接把结点全都保存下来,排了个序,然后重新接起来。如果原来的树是BST,那么中序遍历就相当于是排序,这么做没有什么问题,只是复杂度高点而已。但事实上并不是,所以在心态崩坏中错了三次,最后自己悟出来了可能的原因,交了个看上去像是旋转的方法上去。


很显然可以使用链表之类的数据结构把中序遍历的结点顺序保存下来,然后再重新连接结点,时间复杂度是O(N),额外空间复杂度是O(N)

除此之外,一种简单的方法是在递归中序遍历的基础上修改一下。先递归修改左子树,然后把左子树的最右侧的结点连到当前的根上,然后递归修改右子树,把当前的根的右子树设为递归得到的新子树。我比赛的时候是这么写的,当时自以为是一种“旋转”;但这和一般所说的BST的“旋转”相差有点远,何况这也不是个BST。

上述做法的时间复杂度为O(N^2),因为在最坏情况下(整棵树完全是一个向左延伸的链)枚举左子树最右侧结点的平摊复杂度大致是O(N/2),需要枚举O(N)次。

可以通过一些方法改善这一复杂度,比如在递归修改左子树的时候,把根节点也作为参数传递过去,然后在递归结束时,把根节点连到合适的位置上。[1]

代码

中序遍历(未优化)

比赛的时候脑补出来的代码。

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
41
42
43
44
45
46
47
/**
* 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 {
private:
TreeNode* rotate(TreeNode* root) {
if (root == NULL)
return NULL;
if (root->left == NULL && root->right == NULL)
return root;
TreeNode* newRoot = root;
if (root->left != NULL) {
newRoot = rotate(root->left);
TreeNode* p = newRoot;
while (p->right != NULL) {
p = p->right;
}
p->right = root;
root->left = NULL;
}
if (root->right != NULL) {
root->right = rotate(root->right);
}
return newRoot;
}

void dfs(TreeNode* root) {
if (root == NULL)
return;
dfs(root->left);
cout << root->val << endl;
dfs(root->right);
}

public:
TreeNode* increasingBST(TreeNode* root) {
if (root == NULL)
return NULL;
return rotate(root);
}
};

中序遍历+额外空间

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
/**
* 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 {
private:
vector<TreeNode*> inOrder;

void traverse(TreeNode* root) {
if (root == NULL) return;
traverse(root->left);
inOrder.push_back(root);
traverse(root->right);
}

public:
TreeNode* increasingBST(TreeNode* root) {
traverse(root);
root = NULL;
TreeNode* last = NULL;
for (TreeNode* x: inOrder) {
x->left = x->right = NULL;
if (root == NULL) {
root = last = x;
}
else {
last->right = x;
last = x;
}
}
return root;
}
};

优化的中序遍历

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
/**
* 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 {
private:

TreeNode* traverse(TreeNode* root, TreeNode* tail) {
if (root == NULL) return NULL;
TreeNode* newRoot = root;
if (root->right != NULL)
root->right = traverse(root->right, tail);
else
root->right = tail;
if (root->left != NULL) {
newRoot = traverse(root->left, root);
root->left = NULL;
}
return newRoot;
}

public:
TreeNode* increasingBST(TreeNode* root) {
return traverse(root, NULL);
}
};

上面是我的代码。如果把递归的截止条件下移一层,规整一下,会变得非常好看(但思路可能更不好理解),就像下面这份代码一样:

1
2
3
4
5
6
7
8
9
// author: lee215
// https://leetcode.com/problems/increasing-order-search-tree/discuss/165885/C++JavaPython-Self-Explained-5-line-O(N)
TreeNode* increasingBST(TreeNode* root, TreeNode* tail = NULL) {
if (!root) return tail;
TreeNode* res = increasingBST(root->left, root);
root->left = NULL;
root->right = increasingBST(root->right, tail);
return res;
}

  1. Self-Explained, 5-line, O(N)

题目来源:https://leetcode.com/problems/binary-search-tree-iterator/description/

标记难度:Medium

提交次数:1/1

代码效率:98.53%

题意

写一个二叉搜索树的迭代器,包括初始化、next()hasNext()操作,要求平摊时间复杂度为O(1),空间复杂度为O(h)。

分析

因为空间复杂度是O(h),所以肯定不能把整个树直接存成一个数组然后直接查找,而是要利用树的性质。好吧,其实《数据结构》里在迭代版中序遍历中讲了这个东西。

中序遍历过程

与所有遍历一样,中序遍历的实质功能也可理解为,为所有节点赋予一个次序,从而将半线性的二叉树转化为线性结构。于是一旦指定了遍历策略,即可与向量和列表一样,在二叉树的节点之间定义前驱与后继关系。其中没有前驱(后继)的节点称作首(末)节点。
对于后面将要介绍的二叉搜索树,中序遍历的作用至关重要。相关算法必需的一项基本操作,就是定位任一节点在中序遍历序列中的直接后继。为此,可实现succ()接口如代码5.16所示。

1
2
3
4
5
6
7
8
9
10
11
12
// 代码5.16 二叉树节点直接后继的定位
template <typename T> BinNodePosi(T) BinNode<T>::succ() { //定位节点v的直接后继
BinNodePosi(T) s = this; //记录后继的临时变量
if (rChild) { //若有右孩子,则直接后继必在右子树中,具体地就是
s = rChild; //右子树中
while (HasLChild(*s)) s = s->lChild; //最靠左(最小)的节点
} else { //否则,直接后继应是“将当前节点包含于其左子树中的最低祖先”,具体地就是
while (IsRChild(*s)) s = s->parent; //逆向地沿右向分支,不断朝左上方移动
s = s->parent; //最后再朝右上方移动一步,即抵达直接后继(如果存在)
}
return s;
}

这里,共分两大类情况。若当前节点有右孩子,则其直接后继必然存在,且属于其右子树。此时只需转入右子树,再沿该子树的最左侧通路朝左下方深入,直到抵达子树中最靠左(最小)的节点。
反之,若当前节点没有右子树,则若其直接后继存在, 必为该节点的某一祖先,且是将当前节点纳入其左子树的最低祖先。于是首先沿右侧通路朝左上方上升,当不能继续前进时,再朝右上方移动一步即可。
作为后一情况的特例,出口时s可能为NULL。这意味着此前沿着右侧通路向上的回溯,抵达了树根。也就是说,当前节点是全树右侧通路的终点——它也是中序遍历的终点,没有后继。
(摘自《数据结构(C++语言版)》(第三版),清华大学出版社,2013.9)

我的代码实现得不怎么漂亮,不过里面被注释掉的关键的一句代码path.push(_cur);变相实现了“右侧通路朝左上方上升,当不能继续前进时,再朝右上方移动一步”这个操作:栈中实际上存储的就是经过这个操作之后能够得到的结点,因此右转时的结点是不能入栈的。

代码

我的代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
TreeNode* _root;
TreeNode* _cur;
stack<TreeNode*> path;

public:
BSTIterator(TreeNode *root) {
_root = root;
_cur = root;
// 找到树中最小的结点
while (_cur != NULL && _cur->left != NULL) {
path.push(_cur);
_cur = _cur->left;
}

// cout << _cur->val << endl;
}

/** @return whether we have a next smallest number */
bool hasNext() {
// 和next()的判断逻辑相同:
// 当前结点有右子树,或者仍然有向上回溯的空间
return _cur != NULL;
}

/** @return the next smallest number */
int next() {
int smallest = _cur->val;
// cout << smallest << ' ' << path.size() << endl;
// 寻找_cur的后继
// _cur的右子树不为空,此时后继必为_cur的右子树中最靠左的结点
if (_cur->right != NULL) {
// 必须注释掉这句话,因为path(这个名字起得不好)指的并不是从root到当前结点的路径上的所有结点
// 而是“右子树仍未被访问到的结点”
// path.push(_cur);
_cur = _cur->right;
while (_cur->left != NULL) {
path.push(_cur);
_cur = _cur->left;
}
}
// _cur的右子树为空,此时需要向上回溯
// 因为TreeNode的定义中没有提供父结点指针,所以只好用栈来记录了
// 当然,按照邓公的意见,这样可以省空间,应该是最好的……
else {
if (path.size() > 0) {
_cur = path.top();
path.pop();
}
else
_cur = NULL;
}

return smallest;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

Sample 20ms Submission

我刚发现在提交后的结果页面点时间会得到相应的标程,惊了,Leetcode真是越来越强了。

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
41
42
43
44
45
46
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
stack<TreeNode *> s;
void addToStack(TreeNode * root){
while(root){
s.push(root);
root=root->left;
}
}

BSTIterator(TreeNode *root) {
addToStack(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
return s.size()>0;
}

/** @return the next smallest number */
int next() {
int res = s.top()->val;
TreeNode * top = s.top();
s.pop();
if(top-> right){
addToStack(top->right);
}

return res;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/