題目描述
給定一個二叉樹和其中的一個結(jié)點奖慌，請找出中序遍歷順序的下一個結(jié)點并且返回昼窗。注意累颂，樹中的結(jié)點不僅包含左右子結(jié)點，同時包含指向父結(jié)點的指針谣殊。
/*
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
*/
/*
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;
if(pNode->right!=NULL)//如果有右子樹拂共，找右子樹中的左子樹
{
pNode = pNode->right;
while(pNode->left != NULL){
pNode = pNode->left;
}
return pNode;
}else if(pNode->next!=NULL){//沒有右子樹，節(jié)點是他父節(jié)點的左節(jié)點
TreeLinkNode *tPrent = new TreeLinkNode(pNode->val);
TreeLinkNode *tChild = new TreeLinkNode(pNode->val);
tChild = pNode;
tPrent = pNode -> next;
while(tPrent->left != tChild && tPrent!=NULL ){
tChild = tPrent;
tPrent = tPrent -> next;
}
return tPrent;
}
return NULL;
}
};
