美文网首页
二叉树的下一个结点

二叉树的下一个结点

作者: UAV | 来源:发表于2020-07-04 15:53 被阅读0次

    题目描述

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


    思路

    /*
    1.如果一个结点有右子树,那么它下一个结点就是它右子树中最左边的一个结点。
    2.如果一个结点没有右子树,那么它下一个结点就是它的父结点。
    3.如果一个结点既没有左子树又没有右子树,而且它还是父结点的右子结点。
    我们一直沿着指向父结点的指针一直向上遍历,直到找到一个是它父节点的坐子结点的结点,
    如果这样的结点存在,那么这个父结点就是我们要找到下一个结点。
    */

    /*
    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 == NULL) {
                return NULL;
            }
            TreeLinkNode*pNext = NULL;
    //1.如果一个结点有右子树,那么它下一个结点就是它右子树中最左边的一个结点。
            if (pNode->right != NULL) {
                TreeLinkNode*pRight = pNode->right;
                while (pRight->left!=NULL)
                {
                    pRight = pRight->left;
                }
                pNext = pRight;
            }//父节点不为空
            else if (pNode->next!=NULL) {
                TreeLinkNode* pCurrent = pNode;
                TreeLinkNode*pParent = pNode->next;
                //父节点不为空,且当前结点是父结点的右子结点(有右子树)
                          //******比较链表结点pCurrent==pParent->right
                while (pParent!=NULL&&pCurrent==pParent->right)
                {
                    pCurrent = pParent;
                    pParent = pParent->next;
                }//结点没有右子树,父结点为下一个结点
                pNext = pParent;
            }
            return pNext;
        }
    };
    

    相关文章

      网友评论

          本文标题:二叉树的下一个结点

          本文链接:https://www.haomeiwen.com/subject/puuuqktx.html