递归版

Python 代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.father = None
class Solution(object):
    def inorderSuccessor(self, q):
        """
        :type q: TreeNode
        :rtype: TreeNode
        """
        def dfs(root):
            if root.left:
                return dfs(root.left)
            else:
                return root

        def dfs2(q):
            fa = q.father
            if not fa: return None
            if fa.left == q:
                return fa
            else:
                return dfs2(fa)

        if not q.right:
            return dfs2(q)
        else:
            return dfs(q.right)

迭代版

将递归改成迭代, 大部分情况下, 迭代速度要比递归更快

Python 代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.father = None
class Solution(object):
    def inorderSuccessor(self, q):
        """
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not q.right:
            while q.father and q.father.right == q:
                q = q.father
            return q.father
        else:
            q = q.right
            while q.left:
                q = q.left
            return q