二叉树的下一个节点
题目描述
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
解题思路
- 二叉树的中序遍历的下一个节点
- 如果存在右子树,那么下一个节点就是右子树中的最深的左子树
- 如果不存在右子树,就要回到父节点中。如果是父节点的左子树,那么就是下一个节点,否则,继续向父节点回退。
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode == NULL) return NULL;
TreeLinkNode *pNext=NULL;
if(pNode->right!=NULL){
pNext = pNode->right;
while(pNext->left != NULL)
pNext = pNext->left;
return pNext;
}
while(pNode ->next !=NULL){
if(pNode->next->left==pNode){
return pNode->next;
}
pNode = pNode->next;
}
return pNext;
}
};