1. 首页
  2. 剑指offer经典面试题

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

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

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

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

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

注意:

  • 如果给定的节点是中序遍历序列的最后一个,则返回空节点;
  • 二叉树一定不为空,且给定的节点一定不是空节点;

样例:

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

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

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

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

liwei20191018_1.png

画个清楚的图帮助理解:

liwei20191017_2.png

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

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3257.html

第 33 题:二叉搜索树的后序遍历序列(递归、分治)»

相关推荐

QR code