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

傷城~ 2021-06-24 16:10 368阅读 0赞

**试题：**  
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。  
**代码：**  
这一题的题意是以中序遍历访问二叉树，现在访问到某个给定节点，让你求接下来访问的节点。按照中序规则：  
1、如果当前节点有右子节点的话，那么下一个应该是该右子节点下左叶子节点  
2、如果当前节点没有右子节点的话，此时我们应该去找当前节点的父节点，如果当前节点为父节点的左子节点，那么父节点为下一访问节点；如果为父节点的右子节点，那么我们要继续往上找父节点。

/*
    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){
                pNode = pNode.right;
                while(pNode.left!=null){
                    pNode = pNode.left;
                }
                return pNode;
            }
            while(pNode.next!=null){
                if(pNode.next.left==pNode){
                    return pNode.next;
                }else{
                    pNode = pNode.next;
                }
            }
            return null;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，368人围观）

还没有评论，来说两句吧...

相关阅读

相关 8.【剑指offer】二叉树的下一个结点

[题目][Link 1] 思路： 1. 找到根节点； 1. 存储中序遍历的结果到List集合中； 1. 遍历返回结点 / public cl

清疚/ 2024年03月26日 13:52/ 0 赞/ 76 阅读

相关剑指offer（C++）——二叉树的下一个结点

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

野性酷女/ 2022年06月17日 05:43/ 0 赞/ 161 阅读

相关《剑指offer》--008--二叉树的下一个结点

[《剑指offer》–目录索引][offer] 题目： > 给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以

末蓝、/ 2022年05月27日 04:45/ 0 赞/ 185 阅读

相关剑指offer-题58：二叉树下的一个结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。实验平台：[牛客网][

待我称王封你为后i/ 2022年05月26日 01:14/ 0 赞/ 162 阅读

相关剑指Offer-二叉树的下一个结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。解题思路—回退遍历：要

朴灿烈づ我的快乐病毒、/ 2022年04月24日 13:18/ 0 赞/ 186 阅读

相关【剑指Offer】57二叉树的下一个结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。时间限制：1秒；空间限

曾经终败给现在/ 2022年04月08日 10:42/ 0 赞/ 194 阅读

相关【剑指Offer】（树）二叉树的下一个结点

题目链接：[https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11

朴灿烈づ我的快乐病毒、/ 2022年03月16日 01:12/ 0 赞/ 210 阅读

相关剑指offer：二叉树的下一个结点

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

客官°小女子只卖身不卖艺/ 2022年02月23日 04:24/ 0 赞/ 210 阅读

相关剑指offer 二叉树的下一个结点

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不

迈不过友情╰/ 2021年10月14日 03:40/ 0 赞/ 290 阅读

相关剑指offer：二叉树的下一个结点

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

傷城~/ 2021年06月24日 16:10/ 0 赞/ 369 阅读