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

解体体会：第一次感受到case通过率一步步增加的感受 最终是你的想法更加全面

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext(pNode)
{
    // write code here
    //左叶子是其父节点
    //中间节点是其右孩子的最左孩子或者其父亲
    //右叶子是null或者第一个左祖先的父亲
    
    if(!pNode.left&&!pNode.right){
        if(!pNode.next){
          return null 
        }
        if(pNode.next.left===pNode){//左叶子
            return pNode.next
        }else if(pNode.next.right===pNode){//右叶子
            let point=pNode
            while(point.next){
                if(point.next.right==point){
                    point=point.next
                }else if(point.next.left===point){
                    return point.next
                }
            }
           if(!point.next){
               return null
           }    
        
    }
    }else {
        if (!pNode.right){ //中间节点如果没有右孩子，就返回其父亲
          return pNode.next
        }
        let riChild=pNode.right   //如果有 则返回其右孩子的最左孩子
        while(riChild.left){
            riChild=riChild.left
        }
        return riChild
    }
    
}
module.exports = {
    GetNext : GetNext
};