二叉树的下一个节点
分情况讨论,具体思路详见代码
C++ 代码
# define MaxSize 200
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
// 分情况讨论
// 1. p存在右孩子,后继即为右孩子最左下的节点
if (p->right) {
p = p->right;
while (p->left) p = p->left;
return p;
}
// 2. p不存在右孩子,迭代寻找第一个是左孩子的祖先节点
TreeNode* f = p -> father;
while (f) { // f为空时,说明p已经是根节点了,未找到是左孩子的祖先节点,说明p时最后一个
// 找到返回f
if (p == f->left) return f;
// 未找到继续迭代
p = f;
f = p -> father;
}
return nullptr;
}
};