[剑指offer] 二叉树的下一个结点

题目描述

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

解题思路

中序遍历:左 -> 根 -> 右 分三种情况:

  1. 如果当前节点为空,直接返回空;
  2. 如果当前节点有右子树,则返回右子树的最左子树;
  3. 如果当前节点没有右子树,再分两种情况:
    • 看看当前节点是不是它的父节点的左子树,如果是,则返回它的父节点;
    • 如果当前节点不是它的父节点的左子树,则把父节点赋给当前节点,再判断当前节点是不是它的父节点的左子树,直到当前节点是不是它的父节点的左子树,返回它的父节点。

参考代码

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null){
            return null;
        }
        if(pNode.right != null){
            TreeLinkNode node = pNode.right;
            while(node.left != null){
                node = node.left;
            }
            return node;
        }
        while(pNode.next != null){
            TreeLinkNode root = pNode.next;
            if(pNode == root.left)
                return root;
            pNode = root;
        }
        return null;
    }
}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/getnext/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏工科狗和生物喵

【我的漫漫跨考路】数据结构之单链表线性存储实现 Beta

正文之前 ? 昨天晚上阶段性的完成了一部分数学的复习,所以今天打算撸一撸代码,然后发现提电脑忘指针。所以自己磕磕盼盼,对照了一下网上的代码,总算把线性存储单链表...

36211
来自专栏拂晓风起

java LinkedList ArrayList 随机访问效率 list.get(int index)

1075
来自专栏开发 & 算法杂谈

PAT Advanced 1043

A Binary Search Tree (BST) is recursively defined as a binary tree which has th...

873
来自专栏WindCoder

数据统计第一弹-按时/天/周/月补全某一段时间的数据-Java核心逻辑

本代码均结合之前的发布的DateUtil使用,之后的mysql查询部分看心情发布,就这么任性~ ~

1051
来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

2655
来自专栏WD学习记录

牛客网 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

801
来自专栏趣学算法

数据结构 第12讲 二叉树的层次遍历

二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示:

1113
来自专栏书山有路勤为径

二叉树-最近的公共祖先

已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低(离根最 远),且v,w两个节点都是u的子孙。...

1242
来自专栏Java后端技术栈

为什么MySQL数据库索引选择使用B+树?

在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出...

3631
来自专栏swag code

Calendar类-set()方法的延时操作

set(f,value)方法将日历字段f更改为value,此外还设置了一个内部成员变量,

722

扫码关注云+社区

领取腾讯云代金券