2. 二叉樹的下一個(gè)節(jié)點(diǎn)

二叉樹的下一個(gè)結(jié)點(diǎn)_?？皖}霸_牛客網(wǎng)

題目描述：給定一個(gè)二叉樹其中的一個(gè)結(jié)點(diǎn)，請找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。

示例1:

輸入:{8,6,10,5,7,9,11}, 8
返回:9

1. 如果一個(gè)節(jié)點(diǎn)有右子樹，那么它的下一個(gè)節(jié)點(diǎn)就是它的右子樹的最左節(jié)點(diǎn)
2. 如果一個(gè)節(jié)點(diǎn)沒有右子樹 如果該節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子節(jié)點(diǎn)，那么下一個(gè)節(jié)點(diǎn)就是該節(jié)點(diǎn)的父節(jié)點(diǎn)如果該節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子節(jié)點(diǎn)，那么就一直向上找它的父節(jié)點(diǎn)，直到找到一個(gè)節(jié)點(diǎn)，是父節(jié)點(diǎn)的左孩子節(jié)點(diǎn)，此時(shí)下一個(gè)該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)就是該節(jié)點(diǎn)的父節(jié)點(diǎn)。如果找到根節(jié)點(diǎn)了，就證明到最后了，沒有下一個(gè)節(jié)點(diǎn)了。

class Solution 
{
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) 
    {
        // 1.一個(gè)節(jié)點(diǎn)有右子樹
        if(pNode->right != nullptr) {
            pNode = pNode->right;
            while(pNode->left != nullptr)
                pNode = pNode->left;
            return pNode;
        }
        auto parent = pNode->next;
        // 2.1沒有右子樹, 該節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子節(jié)點(diǎn)
        if(parent != nullptr && parent->left == pNode)
            return parent;
        // 2.2沒有右子樹, 該節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子節(jié)點(diǎn)
        while(parent != nullptr) {
            pNode = parent;
            parent = pNode->next;
            if(parent == nullptr)    break;
            if(pNode == parent->left)
                return parent;
        }
        return nullptr;
    }
};