题目描述 [二叉树的下一个结点]
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路
- 如果该结点有右子树，则该结点的下一个结点为该结点的右子树的最左结点。
- 如果该结点没有右子树：
- 如果该结点为该结点的父结点的左孩子，则该结点的父结点则为下一个结点。
- 如果该结点为该结点的父结点的右孩子，则该结点的父结点的父结点的父结点，直到其中的一个父结点是这个父结点的左孩子，则该父结点的父结点为下一个结点。
代码
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==nullptr) return nullptr;
TreeLinkNode *nextNode = nullptr;
if(pNode->right){
TreeLinkNode *rightNode = pNode->right;
while(rightNode->left){
rightNode = rightNode->left;
}
nextNode = rightNode;
}else if(pNode->next){
TreeLinkNode *parentNode = pNode->next;
while(parentNode && parentNode->left!=pNode){
pNode = parentNode;
parentNode = pNode->next;
}
nextNode = parentNode;
}
return nextNode;
}
};