正文

剑指offer：二叉树的下一节点(代码片段)

le-le  le-le  2023-04-12  146

关键词：

题意描述

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

解题思路

一、暴力解决

分析Node可能在二叉树的所有位置，逐个进行分析。

若node的右子树不为空，中序遍历的下一节点是右子树的最左节点。
若node的右子树为空，左子树不为空，中序遍历的下一节点是父节点。
若node的右子树为空，左子树空，说明是node是叶子节点。
若node为左叶子，中序遍历的下一节点是父节点。
若node是右叶子，中序遍历的下一节点是祖父节点。
特殊情况：①二叉树只有node节点。②斜树。

    public TreeLinkNode GetNext(TreeLinkNode pNode)
        if(pNode == null) return null;  //pNode为空
        if(pNode.right != null)    //右子树不为空
            pNode = pNode.right;    
            while(pNode.left != null) 
                pNode = pNode.left;
            return pNode;   //右子树的最左节点
        else if(pNode.right == null && pNode.left != null)    //右子树为空，左子树不为空
            return pNode.next;  //返回父节点
        else  //左右子树都为空，说明是叶子节点
            if(pNode.next == null) return null; //父节点为空，说明只有一个节点
            if(pNode.next.left == pNode) return pNode.next; //左叶子节点，返回父节点
            else   //右叶子节点
                TreeLinkNode node = pNode.next;
                while(node.next != null)    
                    node = node.next;   //先找到根节点
                while(node.right != null)
                    node = node.right;
                if(node == pNode)
                    return null;    //斜树的右叶子节点
                else
                    return pNode.next.next; //普通情况，右叶子节点返回祖父节点

二、优化

技术图片

如图所示，可以发现

又右子树的，下一节点就是右子树的最左节点。（eg：D，B，E，A，C，G）
没有右子树的，可以分为

（1）父节点的左孩子（eg：N，I，L），父节点就是下一节点

（2）父节点的右孩子（eg：H，J，K，M），向上查找父节点，直到当前节点是父节点的左孩子。如果没有返回尾节点。

     public TreeLinkNode GetNext(TreeLinkNode pNode)
        if(pNode == null) return null;  //pNode为空
         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;  //返回当前节点的父节点
            
             pNode = pNode.next;
         
         return null;   //否则返回null

剑指offer：二叉树的下一个节点(代码片段)

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。classTreeLinkNode:def__init__(self,x):self.val=xself.left=Noneself.right=Noneself.paren... 查看详情

57剑指offer--二叉树的下一结点

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。解题思路：两种情况，若果一个结点有右子树，那么其下一个... 查看详情

剑指offer-二叉树的下一个节点(代码片段)

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 ①节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着... 查看详情

剑指offer（书）：二叉树的下一个节点(代码片段)

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。分析：若一个节点有右子树，那么他的下一个节点就是他右子树中的... 查看详情

剑指offer（57）二叉树的下一个节点(代码片段)

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。题目分析这题一定要画图，因为只有画图我们才能分清楚下一... 查看详情

剑指offer(python)------二叉树的下一个节点(代码片段)

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。这道题意即：给定一个节点，按照中序遍历（左根右）的方式求该... 查看详情

《剑指offer——从中序遍历中找出二叉树的下一个结点》代码(代码片段)

从中序遍历中找出二叉树一个节点的下一个结点问题一、解析问题二、代码解析1.新建.cpp文件我们用如下C++代码从二叉树中找出一个节点的下一个节点（示例）：问题//===========&... 查看详情

剑指offer第7题二叉树的下一个节点

【题目】给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。注意：如果给定的节点是中序遍历序列的最后一个，则返回空节点;二叉树一定不为空，且给定的节点一定不是空节点；样例假定二叉树是：[2,1,3,null... 查看详情

剑指offer-8二叉树的下一个节点

剑指offer-8二叉树的下一个节点题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。思路：右侧有节点，直接打印右侧没... 查看详情

剑指offer-57.二叉树的下一个结点(c++/java)(代码片段)

题目：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。分析：二叉树的中序遍历是左根右，所以如果一个结点的右子树不为... 查看详情

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

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。思路分析二叉树的下一个节点，一共有以下情况：二叉树为空，则... 查看详情

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

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。思路：1）如果一个节点有右子树，那么它的下一个结点就是... 查看详情

[剑指offer]面试题8：二叉树的下一个节点(代码片段)

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。解题思路 1.找到所有的可能情况并归纳，写的代码需... 查看详情

[剑指offer]二叉树的下一个结点(代码片段)

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。题目链接：https://www.nowcoder.com/practice/9023a0c988684a539603... 查看详情

每天一道剑指offer-二叉树的下一个结点(代码片段)

题目每天一道剑指offer-二叉树的下一个结点https://www.nowcoder.com/practice/ef068f602dde4d28aab2b210e859150a?tpId=13&tqId=11215&tPage=4&rp=3&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews 查看详情

剑指offer8二叉树中序遍历的下一个节点(代码片段)

题目给定一个二叉树和其中一个节点，找出中序遍历的下一个节点。注意：树的节点中除了有指向左右节点的指针，还有指向父节点的指针。思路（1）若该节点Node有右子树，则下一个节点就是右子树中的最左节点，就是在右节... 查看详情

剑指offer-二叉树的下一个结点(代码片段)

题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。若结点存在右孩子，则右孩子的最坐下结点为中序遍历下一个... 查看详情

正文