锻练编程思维——每日一题：《剑指offer》二叉树的下一个结点

╰半橙微兮° 2023-02-17 02:20 8阅读 0赞

# 题目描述 #

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

# 题目分析 #

*  这道题是典型的找规律思路，因为你不知道某结点跟下一结点有什么联系。
 *  所以多画几颗二叉树（>=3），然后**找出某结点的下一结点和该某结点的联系**，如图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]
 *  给这些联系归类，**并在二叉树中标明每个结点的下一结点属于哪些联系类。**
 *  看有无联系类可以合并
 *  然后把这些联系类的情况实现成代码形式。

# 题解代码 #

/*
    struct TreeLinkNode {
        int val;
        struct TreeLinkNode *left;
        struct TreeLinkNode *right;
        struct TreeLinkNode *next;
        TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
            
        }
    };
    */
    class Solution {
        
    public:
        TreeLinkNode* GetNext(TreeLinkNode* pNode)
        {
        
            if(!pNode)//空二叉树
            {
        
                return NULL;
            }
            if(pNode->right)//某结点的下一结点为其右孩子结点或右孩子结点的左孩子结点
            {
        
                pNode=pNode->right;
                while(pNode->left)
                {
        
                    pNode=pNode->left;
                }
                return pNode;
            }
            while(pNode->next)//某结点的下一结点为其父结点或其父结点的父结点（该结点是某结点的
            //左孩子结点的右孩子结点）
            {
        
                TreeLinkNode *root=pNode->next;
                if(root->left==pNode)
                {
        
                    return root;
                }
                pNode=pNode->next;
            }
            return NULL;//不属于前两种情况，则某结点是中序遍历的尾结点。
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610202121569.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70