题目描述

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

样例

假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。
2
/ \
1 3

算法1

python3代码

# 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
        """
        #迭代法：分五种情况（详细来说的，用于理解）。
        #1.右子树不为空的就把右子树最左边的节点输出。
        if(q.right):
            q = q.right
            while(q.left):
                q = q.left
            return q
        #2.这里有两种情况：
        #右子树为空：
        #2.1：父节点不为空且一直都是不断迭代然后找不到一个是其父节点的左儿子这样的节点的话就会去到根节点
        #     然后后面直接利用后面的return q.father返回一个None，但是这个None并不是真正实际上的None。
        #     所以这种情况就是输入的一个节点是中序遍历的最后一个节点。
        #2.2：如果迭代过程能够找到一个是其父节点的左儿子这样的节点的话，就退出了while，所以直接利用后面的return q.father
        #     输出该节点的父节点即可。
        #     这种情况是某节点是其左子树最右边的节点的下一个节点。
        while q.father and q == q.father.right:
            q = q.father
        #3.这里也有两种情况：第一种是该二叉树就只有一个节点，所以也是输出它的父节点以取得None，但是并不是实际上的None。
        #                第二种情况是，如果在上面的情况都不符合了，那就运行到这里的return q.father，直接输出父节点就是
        #                它的下一个节点了。也其实就是大佬所谓的“找到第一个是其父节点的左儿子这样的节点，这里的话就是本身了，
        #                所以就是输出它的父节点即可。
        return q.father