厉害，我也要加油刷题，成为你这样厉害的人。

加油！

y总，发现这道题错误的代码也能AC

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if (p->right) {
            p = p->right;
            while (p->left) p = p->left;
            return p;
        }
        if (p->father && p->father->left != p) return NULL;
        return p->father;
    }
};

应该加一些输入节点没有右子树且在它的祖先后继节点的左子树上的数据。

数据已加强，现在这份代码过不去了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        //右子树存在 右子树最左边的结点
        if(p -> right)
        {
            p = p -> right;
            while(p -> left) p = p -> left;
            return p;
        }

        //右子树不存在 只有左子树
        while(p -> father)
        {
            //p不是根节点
            if(p == p -> father -> left)
                return p -> father;
            p = p -> father;
        }

        return NULL;
    }
};

请问为啥y神的最后没加return NULL;叻

返回的p->father有可能是NULL呀。

从找最近的一个比它大的数考虑，比较好想

越往右分叉越大，向右分叉不存在了，说明右到了极点，开始找转弯的地方了
转弯就得往上找，找到把它当作左子树的最右节点的左子树对应的那个父节点，就是开始转弯的地方

y总这代 简洁得无敌

这有点绕口令了

y总
则第一个满足是其father左儿子的节点是F，则F的father就是D的后继。
这里应该是 则C的father F就是D的后继吧

对滴，已更正。

y总，B属于这两种情况的哪一种呢

第二个呀， B不就是father的左儿子

你可以认为第二种情况没有进入while循环就直接到可以找到了，然后直接return B -> father 即可。y总的代码真是越看越秒。

大神，这个题数据量不够，我发现以前写的错误代码也能AC
class Solution {
public:
TreeNode inorderSuccessor(TreeNode p) {
TreeNode* q=p;
if(q->right)
{
q=q->right;
while(q->left)q=q->left;
return q;
}
else
{
if(!q->father||q==q->father->right)return nullptr;
else return q->father;
}
}
};

数据已加强，现在这份代码过不去了。

y哥，这个代码的时间和空间复杂度是多少啊

时间复杂度和额外空间复杂度都是 $O(h)$，$h$ 是树的最大高度。

y神 这里写错了哦！ D的后继是F 如果左子树中某个结点没有右孩子 那么默认根节点是后继。
=======以下是y神的笔记==============
如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。比如当前节点是D，则第一个满足是其father左儿子的节点是C，则C的father就是D的后继。

多谢指正，已修正~

真厉害~

谢谢hh

我晕了 我竟然重新做了一遍中序遍历 理解不到位

加油hh

我写了办天的morris traverse结果发现还有father节点可以用，尴尬

是的hh 练练morris traverse也挺好的，可以加深对树的遍历的理解~

这个morris遍历是啥啊?

可以百度一下，比较复杂的一个算法。

人和人的差别真的是太大了

加油hh

佩服佩服！

谢谢~