[剑指 Offer 第 2 版第 8 题] “二叉树的下一个结点”做题记录

第 8 题：二叉树的下一个结点

传送门：AcWing：二叉树的下一个结点，牛客网 online judge 地址。

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

注意：

如果给定的节点是中序遍历序列的最后一个，则返回空节点;

二叉树一定不为空，且给定的节点一定不是空节点；

样例：

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

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

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

思路：用《算导》中提出的方法，画图分析，把要分类讨论的情况分析清楚，编码就很容易了。这道题的关键在于：看是否有右子树。

画个清楚的图帮助理解：

Python 代码：

  class Solution(object):
        def inorderSuccessor(self, q):
            """
            :type q: TreeNode
            :rtype: TreeNode
            """

            if q is None:
                return None

            # 分类讨论1：如果这个结点有右子树，返回这个右子树的最小者
            if q.right:
                node = q.right
                while node.left:
                    node = node.left
                return node
            # 分类讨论2：如果这个结点没有右子树，向上追溯，追到父亲结点的左结点是自己
            while q.father:
                if q.father.left == q:
                    return q.father
                q = q.father
            return None