LeetCode: 510. 二叉搜索树中的中序后继II¶

1、题目描述¶

输入:
root = {"$id":"1","left":{"$id":"2","left":null,"parent":{"$ref":"1"},"right":null,"val":1},"parent":null,"right":{"$id":"3","left":null,"parent":{"$ref":"1"},"right":null,"val":3},"val":2} p = 1 输出: 2 解析: 1的中序后继结点是2。注意p和返回值都是Node类型的。  示例 2: 输入: root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":1},"parent":{"$ref":"2"},"right":null,"val":2},"parent":{"$ref":"1"},"right":{"$id":"5","left":null,"parent":{"$ref":"2"},"right":null,"val":4},"val":3},"parent":null,"right":{"$id":"6","left":null,"parent":{"$ref":"1"},"right":null,"val":6},"val":5}
p = 6



输入:
root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":2},"parent":{"$ref":"2"},"right":{"$id":"5","left":null,"parent":{"$ref":"3"},"right":null,"val":4},"val":3},"parent":{"$ref":"1"},"right":{"$id":"6","left":null,"parent":{"$ref":"2"},"right":{"$id":"7","left":{"$id":"8","left":null,"parent":{"$ref":"7"},"right":null,"val":9},"parent":{"$ref":"6"},"right":null,"val":13},"val":7},"val":6},"parent":null,"right":{"$id":"9","left":{"$id":"10","left":null,"parent":{"$ref":"9"},"right":null,"val":17},"parent":{"$ref":"1"},"right":{"$id":"11","left":null,"parent":{"$ref":"9"},"right":null,"val":20},"val":18},"val":15} p = 15 输出: 17  示例 4: 输入: root = {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":{"$id":"4","left":null,"parent":{"$ref":"3"},"right":null,"val":2},"parent":{"$ref":"2"},"right":{"$id":"5","left":null,"parent":{"$ref":"3"},"right":null,"val":4},"val":3},"parent":{"$ref":"1"},"right":{"$id":"6","left":null,"parent":{"$ref":"2"},"right":{"$id":"7","left":{"$id":"8","left":null,"parent":{"$ref":"7"},"right":null,"val":9},"parent":{"$ref":"6"},"right":null,"val":13},"val":7},"val":6},"parent":null,"right":{"$id":"9","left":{"$id":"10","left":null,"parent":{"$ref":"9"},"right":null,"val":17},"parent":{"$ref":"1"},"right":{"$id":"11","left":null,"parent":{"$ref":"9"},"right":null,"val":20},"val":18},"val":15}
p = 13



• 如果给定结点不存在中序后继，返回null
• 树中各结点的值均保证唯一。
• 注意我们使用的是Node类型而不是TreeNode类型，它们的字符串表示不一样。

• 你能否在不访问任何结点的值的情况下解决问题?

2、解题思路¶

• 比当前节点大的首先判断右节点，如果存在右节点，就找到右节点的最左节点
• 如果没有右节点，就到父节点中查找第一个大于当前节点值的节点
"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, parent):
self.val = val
self.left = left
self.right = right
self.parent = parent
"""
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Node':
ans = None
if node.right:
ans = node.right
while ans.left:
ans = ans.left
else:
temp = node
while temp and temp.val <= node.val:
temp = temp.parent
ans = temp

return ans

• 拓展

"""
# Definition for a Node.
class Node:
def __init__(self, val, left, right, parent):
self.val = val
self.left = left
self.right = right
self.parent = parent
"""
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Node':
ans = None
if node.right:
ans = node.right
while ans.left:
ans = ans.left
else:
temp = node
while temp.parent and temp.parent.right == temp:
temp = temp.parent
ans = temp.parent
return ans