[数据结构与算法]Acwing19:二叉树的下一个节点

原题地址

二叉树的下一个节点:https://www.acwing.com/problem/content/description/31/

题目：

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。
注意：
1.如果给定的节点是中序遍历序列的最后一个，则返回空节点;
2.二叉树一定不为空，且给定的节点一定不是空节点；
样例

假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。
  2
 / \
1   3

题解

题解思路主要来自y神：https://www.acwing.com/solution/content/714/
我只是记录一下，便于以后复习

这题的思路就是让我们求二叉树中给定节点的后继。

所以我们可以分为两种情况：
1）如果当前节点有右儿子，则右子树中最左侧的节点就是当前节点的后继。比如F的后继是H；
2) 如果当前节点没有右儿子且当前结点是其father结点的右结点，则把他指向它的father结点；当father结点为NULL或者它不在是它父亲结点的右结点时，循环结束，然后再指向它的下一个父节点。例：D的后继结点怎么求：
C的左节点等于D，然后F的左节点不等于C，则循环结束，然后指向C的父节点，则F是D是后继。

代码

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==p->father->right)
            p=p->father;
        return p->father;
    }
};