[数据结构与算法]树-二叉树的下一个结点-JZ57

描述
给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

示例:
输入:{8,6,10,5,7,9,11},8
返回:9
解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来

思路1：暴力

1. 根据给出的结点求出整棵树的根节点
2. 根据根节点递归求出树的中序遍历，存入数组
3. 在数组中查找当前结点，则当前结点的下一结点即为所求
   虽然暴力，但是时间复杂度也是线性的
   第一步：最坏为O(N), N为整棵树结点的个数
   第二步：O(N)
   第三步：最坏为O(N),
   所以整的时间复杂度：3*O(N)

思路2：找规律

中序遍历：左孩子 -> 父亲-> 右孩子
根据规律总结一下：
[2 3 6] 是一类，特点：当前结点有右孩子，那么下一节点就是：右孩子结点的最左孩子结点,如果右孩子结点没有左孩子 就是 右孩子自己
[1] 是一类：特点：当前结点没有右孩子，自身是父亲结点的左孩子，下一节点就是：父亲结点
[4 5]是一类，特点：当前结点没有右孩子，自身为父亲结点的右孩子，由于父亲节点本身已经被遍历过，所以本质还是[1]那一类
[7]是一类，特点：最尾结点 返回null

时间复杂度：最坏情况下为O(N)
空间复杂度：O(1)
代码

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }
        // [2 3 6]类 当前节点有右孩子
        if (pNode.right != null) {
            pNode = pNode.right;
            while(pNode.left != null) {
                pNode = pNode.left;
            } 
            return pNode;
        }
        // [1] 和 [4 5] 类 没有右孩子,往上找父类
        while(pNode.next != null) {
            TreeLinkNode root = pNode.next;
            if (root.left == pNode) {
                return root;
            }
            pNode = pNode.next;
        }
        return null;
    }
}