题解 | #二叉树的下一个结点#
二叉树的下一个结点
http://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e
/* 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 *dad=pNode->next;
if(dad==NULL) //为根节点的情况，其父节点为NULL
{
dad=pNode->right;
if(dad==NULL) //只有根节点一个元素的情况
return NULL;
while(dad->left!=NULL) //在根节点右边集群中找到最底层的左子树节点
dad=dad->left;
return dad;
}
else{ //不为根节点的情况
if(dad->left==pNode) //pNode为父节点的左节点的情况
{
if(pNode->right!=NULL)
{
dad=pNode->right;
while(dad->left!=NULL)
dad=dad->left;
return dad;
}
else
return pNode->next;
}
else //pNode为父节点右节点的情况
{
if(pNode->right!=NULL)
{
dad=pNode->right;
while(dad->left!=NULL)
dad=dad->left;
return dad;
}
else //注意当pNode的右子节点为空时，pNode可能在根节点左边最底层的最右节点上
{
TreeLinkNode *son=pNode;
dad=pNode->next;
while(dad!=NULL)
{
if(dad->left==son)
return dad;
son=dad;
dad=son->next;
}
return NULL;
}
}
}
}
};
投递嘉士伯等公司10个岗位