二叉樹的下一個結點

時間限制：1秒空間限制：32768K
通過比例：26.00%
最佳記錄：0 ms|8552K（）

題目描述
給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點並且返回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。

思路：首先知道中序遍歷的規則是：左根右，然後作圖

結合圖，我們可發現分成兩大類：1、有右子樹的，那麼下個結點就是右子樹最左邊的點；（eg：D，B，E，A，C，G） 2、沒有右子樹的，也可以分成兩類，a)是父節點左孩子（eg：N，I，L） ，那麼父節點就是下一個節點 ； b)是父節點的右孩子（eg：H，J，K，M）找他的父節點的父節點的父節點...直到當前結點是其父節點的左孩子位置。如果沒有eg：M，那麼他就是尾節點。

/**
題目描述

給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點並且返回。
注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。

*/
#include<cstdio>
using namespace std;

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;
//左根右
if(pNode->right)//有右子樹，找右子樹的最左的結點
{
pNode=pNode->right;
while(pNode->left) pNode=pNode->left;
pNext=pNode;
}
else if(pNode->next)//分兩種情況 H、J、K 和 M
{
TreeLinkNode* pParent=pNode->next;
while(pParent && pNode==pParent->right)
{
pNode=pParent;
pParent=pParent->next;
}
pNext=pParent;
}

return pNext;
}
};
int main()
{
return 0;
}