07_二叉树的下一个节点

要求： 给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？ 树中的结点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
思路：将结点归为三种类型
1、有右子树，则它的下一结点是右子树的最左结点
2、无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点
3、无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，
如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。

例：以该二叉树为例，中序遍历为：{D,B,H,E,I,A,F,C,G}

二叉树
仔细观察，可以把中序下一结点归为几种类型：

1. 有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
2. 无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
3. 无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点

// 二叉树结构
class TreeLinkNode{
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null; // 父结点
    TreeLinkNode(int val) {
        this.val = val;
    }
}
public TreeLinkNode L07_GetNext(TreeLinkNode pNode){
        // 1.有右子树，则它的下一结点是右子树的最左结点
        if (pNode.right != null) {
            TreeLinkNode pRight = pNode.right;
            while (pRight.left != null) {
                pRight = pRight.left;
            }
            return pRight;
        }
        // 2.无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }
        // 3.无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，
        //如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。
        if (pNode.next != null) {
            TreeLinkNode pNext = pNode.next;
            while (pNext.next != null && pNext.next.right == pNext) {
                pNext = pNext.next;
            }
            return pNext.next;
        }
        return null;
    }