面試高頻算法題補充系列：二叉樹的下一個節點

前言

了解更多常考高頻算法題可以關注

公衆号：一個搬磚的胖子

企業面試題庫:https://codetop.cc/

小程式：CodeTop

今天補充的題目雖是劍指offer的題，但Leetcode上沒有。

題目描述

給定二叉樹其中的一個結點，請找出其中序周遊順序的下一個結點并且傳回。

注意，樹中的結點不僅包含左右子結點，而且包含指向父結點的指針。

題目分析

以下解析參考牛客@劉豪傑，思路非常清晰。

節點(設為x)中序周遊的下一個節點有以下可能：

1.若x有右子樹。則x的下一個節點為x右子樹最左側節點。如，2的下一個節點為8。

2.若x沒有右子樹，又分為2種情況。

• 若x是父節點的左孩子。則x的父節點就是x的下一個節點。如，7的下一個節點是4。
• 若x是父節點的右孩子。則沿着父節點向上，直到找到一個節點的父節點的左孩子是該節點，則該節點的父節點就是x的下一個節點。如，9的下一個節點是1。

我個人覺得這題并不簡單。之前我也做過這道題，但是這兩天去做，又遺漏了一種情況。看來重複刷題真的很重要！！

掌握了的話，送出代碼試試~

//參考牛客@weizier的JAVA代碼
/*
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->right) { //如果有右子樹，則找右子樹的最左節點
            TreeLinkNode *p = pNode->right;
            while(p->left) p = p->left;
            return p;
        }
        TreeLinkNode *p = pNode;
        while(p->next) { //沒右子樹，則找第一個目前節點是父節點左孩子的節點
            if(p->next->left == p) return p->next;
            p = p->next;
        }
        return nullptr; //退到了根節點仍沒找到，則傳回null
    }
};
           

參考連結

https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e

https://mp.weixin.qq.com/s/ug9KoqbrVFMPBTqX-ZaKbA