# 【LeetCode 二叉树专项】二叉搜索树中的中序后继（285）

## 1. 题目

### 1.1 示例

• 示例

1

1

1

• 输入： root = [2,1,3]p = 1
• 输出：

2

2

• 解释： 这里

1

1

的中序后继是

2

2

。请注意 p 和返回值都应是 TreeNode 类型。

• 示例

2

2

2

• 输入： root = [5, 3, 6, 2, 4, null, null, 1]p = 6
• 输出： null
• 解释： 因为给出的节点没有中序后继，所以答案就返回 null 了。

### 1.3 限制

• 树中节点的数目在范围

[

1

,

1

0

4

]

[1,text{ }10^4]

内；

• 1

0

5

<

=

Node.val

<

=

1

0

5

-10^5 <= text{Node.val} <= 10^5

• 树中各节点的值均保证唯一。

## 2. 解法一（递归中序遍历）

### 2.2 实现

from typing import Optional

class TreeNode:
def __init__(self, val: int, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def __init__(self):
self._nodes = []

def _inorder(self, root: TreeNode):
if root is None:
return
self._inorder(root.left)
self._nodes.append(root)
self._inorder(root.right)

def initialize(self):
self._nodes = []

def successor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
self._inorder(root)
index = self._nodes.index(p)
if index >= len(self._nodes) - 1:
return
else:
return self._nodes[index + 1]

def main():
node6 = TreeNode(1)
node5 = TreeNode(4)
node4 = TreeNode(2, left=node6)
node3 = TreeNode(6)
node2 = TreeNode(3, left=node4, right=node5)
node1 = TreeNode(5, left=node2, right=node3)
root = node1
sln = Solution()

def print_successor(suc: TreeNode):
if suc:
print(suc.val)
else:
print(None)

print_successor(sln.successor(root, node6))  # 2
sln.initialize()
print_successor(sln.successor(root, node2))  # 4
sln.initialize()
print_successor(sln.successor(root, node5))  # 5
sln.initialize()
print_successor(sln.successor(root, node3))  # None

if __name__ == '__main__':
main()



from typing import Optional

class TreeNode:
def __init__(self, val: int, left=None, right=None):
self.val = val
self.left = left
self.right = right

class ElegantSolution:
def __init__(self, root: TreeNode):
self._nodes = []
self._inorder(root)

def _inorder(self, root: TreeNode):
if root is None:
return
self._inorder(root.left)
self._nodes.append(root)
self._inorder(root.right)

def successor(self, p: TreeNode) -> Optional[TreeNode]:
index = self._nodes.index(p)
if index >= len(self._nodes) - 1:
return
else:
return self._nodes[index + 1]

def print_successor(suc: TreeNode):
if suc:
print(suc.val)
else:
print(None)

def main():
node6 = TreeNode(1)
node5 = TreeNode(4)
node4 = TreeNode(2, left=node6)
node3 = TreeNode(6)
node2 = TreeNode(3, left=node4, right=node5)
node1 = TreeNode(5, left=node2, right=node3)
root = node1

sln = ElegantSolution(root)
print_successor(sln.successor(node6))  # 2
print_successor(sln.successor(node2))  # 4
print_successor(sln.successor(node5))  # 5
print_successor(sln.successor(node3))  # None

if __name__ == '__main__':
main()



### 2.3 复杂度

• 时间复杂度：

O

(

n

)

O(n)

，因为要先遍历所有节点得到中序遍历序列；

• 控件复杂度：

O

(

n

)

O(n)

，因此至少需要一个实例属性 _nodes 来保存所有节点。

## 3. 解法二（迭代中序遍历）

### 3.1 分析

• 如果当前节点有右子节点的话，中序后继在当前节点之下，如下图中红色节点所示；
• 如果当前节点没有右子节点的话，中序后继在当前节点之上，如下图中蓝色节点所示。

O

(

h

)

O(h)

O(h) ，其中

h

h

h 为树的高度。在第一种情况下也可以用中序遍历的方法，但之前的方法更快一点。

### 3.2 实现

from typing import Optional

class TreeNode:
def __init__(self, val: int, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def inorder_successor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
if root is None or not isinstance(root, TreeNode):
return
if p.right:
node = p.right
while node.left:
node = node.left
return node

stack, prev = [], float('-inf')
cursor = root
while True:
if cursor:
stack.append(cursor)
cursor = cursor.left
elif stack:
node = stack.pop()
if prev == p.val:
return node
prev = node.val
cursor = node.right
else:
break
return

def print_successor(suc: TreeNode):
if suc:
print(suc.val)
else:
print(None)

def main():
node6 = TreeNode(1)
node5 = TreeNode(4)
node4 = TreeNode(2, left=node6)
node3 = TreeNode(6)
node2 = TreeNode(3, left=node4, right=node5)
node1 = TreeNode(5, left=node2, right=node3)
root = node1
sln = Solution()

print_successor(sln.inorder_successor(root, node6))  # 2
print_successor(sln.inorder_successor(root, node2))  # 4
print_successor(sln.inorder_successor(root, node5))  # 5
print_successor(sln.inorder_successor(root, node3))  # None

if __name__ == '__main__':
main()



### 3.3 复杂度

• 时间复杂度： 如果节点 p 有右子节点，时间复杂度为

O

(

h

p

)

O(h_p)

，其中

O

(

h

p

)

O(h_p)

是节点 p 的高度。如果没有右子节点，时间复杂度为

O

(

H

)

O(H)

，其中

h

h

为树的高度；

• 空间复杂度： 如果节点 p 有右子节点，空间复杂度为

O

(

1

)

O(1)

。如果没有右子节点，空间复杂度度为

O

(

h

)

O(h)

from typing import Optional

class TreeNode:
def __init__(self, val: int, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def inorder_successor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
if root is None or not isinstance(root, TreeNode):
return
if p.right:
node = p.right
while node.left:
node = node.left
return node

successor = None
while root:
if root.val < p.val:
root = root.right
elif root.val > p.val:
successor = root
root = root.left
else:
break
return successor


O

(

1

)

O(1)

O(1)

THE END

)">