1. 分情况列举

1.1 分析

1. 有右孩，返回右子树的中序最左结点
2. 无右孩,且它是父亲的左孩，则返回其父
3. 无右孩，且它是其父亲的右孩，则从它父亲开始往上找, 直到某个结点，它是其父亲的左孩，返回其父亲。

1.2 代码

/*
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)
    {
        //1. 有右孩，返回右子树的中序最左结点
        if(pNode.right != null){
            TreeLinkNode node = pNode.right;
            while(node.left != null){
                node = node.left;
            }
            return node;
        }
        //2. 无右孩,且它是父亲的左孩，则返回其父
        if(pNode.next != null && pNode == pNode.next.left){
            return pNode.next;
        }
        //3. 无右孩，且它是其父亲的右孩，则从它父亲开始往上找
        //直到某个结点，它是其父亲的左孩，返回其父亲
        if(pNode.next != null && pNode == pNode.next.right){
            TreeLinkNode node = pNode.next;
            while(node.next != null && node.next.left != node){
                node = node.next;
            }
            return node.next;
        }
        //4. 没有右孩的根节点
        return null;
    }
}

1.3 复杂度

空间：O(1)
时间：O(h), h = log_n