专栏首页小浩算法《剑指offer》第七天:二叉树的下一个结点

《剑指offer》第七天:二叉树的下一个结点

二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

解法

对于结点 pNode

  • 如果它有右子树,则「右子树的最左结点」就是它的下一个结点;
  • 如果它没有右子树,判断它与父结点 pNode.next 的位置情况:
    • 如果它是父结点的左孩子,那么父结点 pNode.next 就是它的下一个结点;
    • 如果它是父结点的右孩子,一直向上寻找,直到找到某个结点,它是它父结点的左孩子,那么该父结点就是 pNode 的下一个结点。
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/

public class Solution {
    /**
     * 获取中序遍历结点的下一个结点
     * @param pNode 某个结点
     * @return pNode的下一个结点
     */
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        
        if (pNode.right != null) {
            TreeLinkNode t = pNode.right;
            while (t.left != null) {
                t = t.left;
            }
            return t;
        }
        
        // 须保证 pNode.next 不为空,否则会出现 NPE
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }
        
        while (pNode.next != null) {
            if (pNode.next.left == pNode) {
                return pNode.next;
            }
            pNode = pNode.next;
        }
        
        return null;
        
    }
}

测试用例

  1. 普通二叉树(完全二叉树;不完全二叉树);
  2. 特殊二叉树(所有结点都没有左/右子结点;只有一个结点的二叉树;二叉树的根结点为空);
  3. 不同位置的结点的下一个结点(下一个结点为当前结点的右子结点、右子树的最左子结点、父结点、跨层的父结点等;当前结点没有下一个结点)。

我把我写的所有题解整理成了一本电子书放在了 github 上,三天内冲击到 github 排行榜榜首!近 5w 人下载阅读!要获取的话,直接进入下方链接就可以了(记得给我点个 star):

https://github.com/geekxh/hello-algorithm

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 万字长文!剑指offer全题解思路汇总

    面试题1:赋值运算符重载:该题主要考察 拷贝构造,构造析构,重载操作符。在面试者使用 c++ 等语言时进行考察。

    程序员小浩
  • 《剑指offer》第六天:重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,...

    程序员小浩
  • 一道魔性的贪心题目(随意吐槽)

    假设你是一位很棒(多棒???)的家长,想要给你的孩子们一些小饼干(不能给大饼干吗???)但是,每个孩子最多只能给一块饼干(有毒吧。。。)

    程序员小浩
  • 二叉树的下一个结点&二叉树的上一个结点

     最笨的方法就是一直网上回溯,直到找到了头结点,然后从头结点开始重新中序遍历一次树,然后得到答案  还有一种比较巧妙的方法,先判断当前结点有没有右子树,如果有...

    mathor
  • 这 30 张图带你读懂红黑树

    本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难...

    帅地
  • 「学习笔记」树和二叉树

    由 n(n ≧ 0)个结点组成的有序集合,n = 0 时称为空二叉树;n > 0 的二叉树是由一个根节点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。...

    FoamValue
  • 数据结构 | 每日一练(39)

    ——老子

    闫小林
  • 30 张图带你彻底理解红黑树

    小吴正在写红黑树的相关系列文章,不过内容太多,动画做起来比较慢,大家可以先看一下这篇红黑树的介绍,内容很不错。

    五分钟学算法
  • 30 张图带你彻底理解红黑树

    本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难...

    智能算法
  • 图解红黑树

    红黑树(Red Black Tree)是一种含有红黑结点并能自平衡二叉查找树,典型的用途是实现 map。

    Dabelv

扫码关注云+社区

领取腾讯云代金券