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

/* 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) {
//有右节点返回右节点的最左节点
    if(pNode.right != null){
        return getMostLeft(pNode.right);
    }
//无右节点，当该节点是父节点的左节点时返回父节点
//pNode.next != null语句可以处理最后一个节点没有下一个节点的特殊情况
    else {
        while(pNode.next != null && pNode.next.left != pNode){
            pNode = pNode.next;
        }
        return pNode.next;
    }
}

public static TreeLinkNode getMostLeft(TreeLinkNode curNode){
    while(curNode.left != null){
        curNode = curNode.left;
    }
    return curNode;
}

}