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

1. 第一种方法

写出树的中序遍历

// function TreeLinkNode(x){
//     this.val = x;
//     this.left = null;
//     this.right = null;
//     this.next = null;
// }
var zlist = []
function GetNext(pNode)
{
    // write code here
    var newnode = pNode
    while(newnode.next !== null) {
        newnode = newnode.next
    }
    InOrder(newnode)
    var pindex = zlist.indexOf(pNode)
    return zlist[pindex + 1]
}
function InOrder(node) {
    if(node !== null) {
        InOrder(node.left)
        zlist.push(node)
        InOrder(node.right)
    }
    
}
module.exports = {
    GetNext : GetNext
};

2. 第二种方法（寻找结点的下一结点）

分为三种情况：

有右子树

无右子树，在左节点

无右子树，在右结点

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext(pNode)
{
    // write code here
    //有右子树
    if(pNode.right!==null) {
        var newnode = pNode.right
        while(newnode.left !== null) {
            newnode = newnode.left
        }
        return newnode
    }
    // 没有右子树
    else {
        if(pNode.next === null) {return null}
         // 在左结点
        if(pNode.next.left === pNode) {
            return pNode.next
        }
        // 在右结点
        else{
            var newnode = pNode
            while(newnode.next.left !== newnode) {
                newnode = newnode.next
                if(newnode.next === null) {
                    return null
                }
            }
            return newnode.next
        }
    }
}
module.exports = {
    GetNext : GetNext
};