思路
求一个结点的后继结点需要考虑两种情况:
1、此结点有右子树:如果有右子树,那么此结点的后继结点就是右子树最左下角的元素;
2、此结点没有右子树:如果没有右子树,那么后继结点一定在双亲结点中,一直向上找,直到某个结点p是其直接双亲q的左子树,那么这个q结点即为所求;
C++ 代码
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
if(p->right){
p = p->right;
while(p->left) p = p->left;
return p;
}
TreeNode* q = p->father;
while(q && q->left != p){
p = q, q = q->father;
}
return q;
}
};