题目
给定一棵二叉树和其中的一个结点, 求该结点的中序遍历后继, 结点定义如下:
1
2
3
4
5
6
7
8
9
10
| class Node {
int val;
Node left;
Node right;
Node parent;
public Node(int val) {
this.val = val;
}
}
|
题解
结点的中序后继有以下几种情况:
- 结点有右子树: 该节点的中序后继即为其右子树最左的结点, 如头图中 1 的后继即为 6
- 结点没有右子树: 则需一直向上查找, 直到某个结点为其父结点的左子树为止, 其后继即为该父节点, 如 5 的后继为 1; 若无满足条件的结点则返回 null, 如 7 无后继
Java
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
| public class FindSuccessor {
public static Node findSuccessor(Node node) {
if (node == null)
return null;
if (node.right != null) {
return getLeftMost(node.right);
} else {
Node parent = node.parent;
while (parent != null && parent.left != node) {
node = parent;
parent = node.parent;
}
return parent;
}
}
public static Node getLeftMost(Node node) {
if (node != null){
while (node.left != null) {
node = node.left;
}
}
return node;
}
}
|
Python
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
| class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
class FindSuccessor:
def get_successor(self, node):
if not node:
return None
if node.right:
return self.get_left_most(node.right)
else:
parent = node.parent
while parent and parent.left != node:
node = parent
parent = node.parent
return parent
def get_left_most(self, node):
if node:
while node.left:
node = node.left
return node
|