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