Successor: Write an algorithm to find the “next” node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.
Hints: #79, #91
解法1
这个题目的意思是，如果我们从一个node开始做中序遍历，那么这个节点的下一个被遍历到的节点是哪个？
先看中序遍历是啥意思：
1
2
3
4
5
|
public void inOrder(Node node) {
inOrder(node.left);
visit(node);
inOrder(node.right);
}
|
举个例子：
1
2
3
4
5
6
7
8
|
1
/ \
2 3
/ \ / \
4 5 6 7
中序遍历的结果是：4、2、4、1、6、3、7
1的下一个节点是6
|
其实这个问题可以发现一个节点的中序遍历的下一个节点就是其右子树的最左边节点。
如果这个node没有右子树，那么得找上一个节点，举个例子：
1
2
3
4
5
|
1
/ \
2 3
/ / \
4 6 7
|
我们要找2的下一个节点，那么它的下一个节点是1，为什么？因为题目里说了一个Node可以访问parent，从1的角度来说，从它开始的中序遍历顺序是4、2、1、6、3、7，看到没有？2的后面是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
|
1
/ \
2 3
/
4
找4的下一个
中序结果是：4、2、1、3
4的下一个是2
1
/ \
2 3
/
4
找4的下一个
中序结果：2、1、4、3
4的下一个是3
1
/ \
2 3
\
4
找4的下一个
中序结果是2、4、1、3
4的下一个是1
1
/ \
2 3
\
4
找4的下一个
中序结果是：2、1、3、4
4的下一个是null
|
发现的规律是这样的，比较拗口：
- 不断从4开始找祖先
- 找到一个祖先是某个节点的左节点
- 那这个某个节点就是4的下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public Node successor(Node node) {
if (node.right != null) {
return leftMost(node.right);
}
return nextNode(node);
}
public Node leftMost(Node node) {
if (node.left == null) {
return node;
}
return leftMost(node.left);
}
public Node nextNode(Node node) {
if (node.parent == null) {
return null;
}
if (node == node.parent.left) {
return node.parent;
}
return nextNode(node.parent);
}
|
总结
关于这个node没有右子树找它下一个节点的办法：
根据中序遍历的定义，遍历顺序是 left -> parent -> right，如果【当前节点n】是它parent node的左节点，那么它的下一个就是parent node。
如果它是parent的右节点，那么parent以及left都在它之前遍历过了。那么它下一个遍历的是什么？肯定不是parent，也不会是parent的parent，也就只能是它的祖先是某个node的左节点的时候，这个node才是它的下一个遍历的node。
评论