暴力解法当然就是按照中序遍历一遍,但这题中参数只给了待查找的子树根节点,中序遍历操作过于麻烦,最好是从子树根节点直接开始查找。
-
如果子树根节点存在右节点,则从该右节点开始,一路向左查找;
-
否则,子树根节点的中序遍历下一个节点只能在其父辈中查找,并且只有将当前根节点作为左节点的父节点符合条件:
-
往上查找,找到第一个把当前根节点当做左子节点的父节点;
-
如果不存在,则待查找子树根节点是该树中序遍历的最后一个节点,返回NULL。
-
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
if(!pNode)
return NULL;
TreeLinkNode* temp = NULL;
if(pNode->right){
temp = pNode->right;
while(temp->left){
temp = temp->left;
}
}
else if(pNode->next){
while(pNode->next && pNode->next->right == pNode){
pNode = pNode->next;
}
temp = pNode->next;
}
return temp;
}
};