题目描述

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

分析

对于二叉树中序遍历来说,某node的下一个节点可以分为以下几种情况:

  1. node.right 不为 null时,根据中序遍历的定义,下一个节点则是node右子树里最左边的节点。
  2. node.right 为 null时,考察node是否为node.parent的左节点,如果是的话,node的下一个节点就是node.parent;否则,考察node.parent是否为node.parent.parent的左节点,依次这样向上探索下去。

代码实现

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext(node)
{
    if(node === null)
        return null;
    if(node.right !== null){
        node = node.right;
        while(node.left !== null){
            node = node.left;
        }
        return node;
    }else{
        while(node.next !== null){
            if(node === node.next.left)
                return node.next;
            node =  node.next;
        }
    }
    return null;
}

本文固定链接: http://www.js-code.com/node-js/node-js_29835.html