题解 | #二叉树的下一个结点#

O(N), O(1)

• 分类讨论，切记中序遍历，为左根右，因为需求给定结点的下一个结点，所以我们只需要讨论给定结点的右子树部分。同样扩展来说，要求给定的结点的上一个结点，只需要讨论给定结点的左子树部分

分析基于题中此图

(1), pNode.right == null, 例如g结点，我们应该是沿着next往回找，且要保证往回找的结点都是遍历过的，所以加上这一判别条件，pNode.next.right == pNode，因为中序遍历-左中右，沿着next往回找的结点其实是“中”，所以是遍历过的。最后找到结点a,返回a.next即null。 可以用l结点对比来看，为什么要加那一判别条件.

(2), pNode.right != null, 例如b结点，返回以pNode.right为跟结点的子树的中序遍历的第一个结点。即是其中序遍历的下一个结点，h结点

public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode) {//中序遍历,左根右
    if(pNode.right == null){
        while(pNode.next != null && pNode.next.right == pNode){//mark
            pNode = pNode.next;
        }
        return pNode.next;
    }else{
        return getStart(pNode.right);
    }

}

public TreeLinkNode getStart(TreeLinkNode root){//正常中序遍历中，第一个结点
    if(root == null) return root;
    
    while(root.left != null){
        root = root.left;
    }
    
    return root;
}
}