JavaScript求解二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

实现思路

中序遍历的顺序 左 - 根 - 右，所以寻找下一个节点的优先级应该反过来 优先级 右 - 根 - 左。
根据二叉树中序遍历的特点，可以分为以下几种情况。

1. 如果结点为空，则直接返回；
2. 如果右子结点不为空，则找到右结点的最左侧结点，即为下一个结点；
3. 如果右结点为空，考虑以下情况：
   • 结点为父节点的左结点，那么父节点就是下一个结点；
   • 结点为父节点的右结点，说明父节点被遍历过，就再往上层寻找...，直至找到符合条件的父结点或父节点为空。

JavaScript代码实现如下：

function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}
function GetNext(pNode)
{
    if(!pNode) {
        return null;
    }
    let pNext = null;
    if(pNode.right) {
        pNode = pNode.right;
        while(pNode.left) {
            pNode = pNode.left;
        }
        pNext = pNode;
    } else {
        let pCurrent = pNode, pParent = pNode.next;
        while(pParent && pCurrent === pParent.right) {
            pCurrent = pParent;
            pParent = pParent.next;
        }
        pNext = pParent;
    }
    return pNext;
}
module.exports = {
    GetNext : GetNext
};