【剑指offer】二叉树的下一个结点

思路：看到这种题，先画出一颗满二叉树，写出中序序列；观察某个节点的下一个节点的位置。
看出端倪后，画一个残缺的二叉树，找出规律求解即可。

讨论：

1. 当前节点有右子树
2. 当前节点无右子树
   2.1 当前节点是父节点的左子树
   2.2 当前节点是父节点的右子树

// 分析问题，找出归路。很考验基本功了...

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;
        }

        if (pNode.right != null) { //1.当前节点有右子树
            pNode = pNode.right;
            while (pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        } else { // 2.当前节点无右子树
            while (pNode.next != null) {
                if (pNode.next.left == pNode) { // 2.1 当前节点是父节点的左子树
                    return pNode.next;
                } else { // 2.2 当前节点是父节点的右子树
                    pNode = pNode.next;
                }
            }
            return null;
        }
    }
}