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

朴灿烈づ我的快乐病毒、 2022-03-16 01:12 229阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_9023a0c988684a53960365b889ceaf5e_tpId_13_tqId_11210_tPage_3_rp_3_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法 ####

/* 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)
        { 
            TreeLinkNode *res=nullptr;
            if(!pNode) return res;
            //情况1：该节点有右子树
            if(pNode->right){ 
                TreeLinkNode *temp=pNode->right;
                while(temp->left) temp=temp->left;
                res=temp;
            }
            else if(pNode->next){ 
                //情况2：该节点没有右子树，且是其父节点的左孩子
                if(pNode==pNode->next->left) 
                    res=pNode->next;
                //情况3：该节点没有右子树，且是其父节点的右孩子
                else{ 
                    TreeLinkNode *temp=pNode->next;
                    if(!temp->next) return nullptr;
                    while(temp==temp->next->right){ 
                        temp=temp->next;
                        if(!temp->next) return nullptr;
                    } 
                    res=temp->next;
                }
            }
            return res;
            
        }
    };

[https_www.nowcoder.com_practice_9023a0c988684a53960365b889ceaf5e_tpId_13_tqId_11210_tPage_3_rp_3_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking