题目描述:

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

其中树的结构如下:

public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;  //指向父节点的指针

    TreeLinkNode(int val) {
        this.val = val;
    }
}

1.对于这道题,一开始我想到的是直接中序遍历,然后把中序遍历的结果保存到一个数组里,然后根据所给的节点依次匹配数组里的值,如果对应的话,输入数组的下一个节点即可,当然输出之前需要判断下一个节点是否存在.
2.其实,保存在数组不是必要的，使用中序遍历，从根节点找到了该节点之后，获得下一个节点返回即可.可以通过设置一个flag来实现

但是这样是否有一个问题?先不说第一种的复杂度,当存在两个节点值相同的时候,这种做法似乎不一定能保证结果正确.(但这题好像也不太会出相同节点,不然返回值是多个,那么题目应该会要求返回一个list,而题目要求返回的是一个节点)

最后,还是得回到题目真正要考察的点吧,不然收获的就是一个"今天面试就这样了,回去等通知吧"

现在回归正题:中序遍历是 : 左根右 所以,对于中序排序假设如下图:

image.png

由图可以看到,找下一个节点可以分为几种情况的:
第一种情况:就是一个节点有右子树

比如,要求节点B的下一个节点,其实是找到它的右子树的最左孩子,就是G节点.

第二种情况:就是一个节点没有右子树,此时可以分为两种情况讨论

1.对于G这个节点来说, 没有右子节点了,它的父亲节点是E,G是E的左子节点,即E的左子节点是G,那么G的下一个节点就是E.

2.对于E这个节点来说，也没有右子节点，它的父亲节点是B，此时E是B的右子节点,根据中序遍历的规则,E肯定在B之后.因此需要找B以上的父亲节点才会是E的下一个节点

所以，对于一个没有右子节点的节点来说，只需要判断它有没有父节点并且是不是父节点的左子节点，是的话，就找到了，不是则要不断地向上找。

如果一直找到根还是找不到，像节点F，那就返回null，因为实际上F节点就是中序遍历的最后一个节点，没有所谓的下一个节点了。

总之，我们不关心当前节点的左子节点，因为它不在我们的考虑范围内，它必定出现在当前节点的前面。

我们主要就是考虑有没有右子节点，或者没有右子节点的话就考虑父亲节点。有右子节点比较简单，一直找最左边的子节点即可。但是没有右子节点的时候，就需要去查询父亲节点了。理解了这些，程序也就呼之欲出了：

class Solution53 {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) return null;
        if (pNode.right != null) {
            pNode = pNode.right; //以当前右子树为入口,一直找右子树的最左节点
            while (pNode.left != null) pNode = pNode.left;
            return pNode; 
        }

        //如果没右子树,则找第一个当前节点(B)是父亲节点(A)的左孩子的节点(A)
        //如E的父亲节点B的父亲节点是A,即A的左孩子是B,则E的下一个节点是A
        while (pNode.next != null) {

            //当前节点是不是父亲节点的左孩子,是的话,父亲节点就是下一个节点
            if (pNode == pNode.next.left) return pNode.next;
            pNode = pNode.next; //往上查找父亲节点
        }

        return null;  //退到了根节点仍没找到，则返回null
    }
}