二叉树的下一个结点、二叉树测试用例编写

[TieMuZhen]

JZ8 二叉树的下一个结点

描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

/*function TreeLinkNode(x){
    this.val = x;
    this.left = null;
    this.right = null;
    this.next = null;
}*/
function GetNext(pNode){
    // 如果pNode有右子树，则返回右子树最左边的节点
    // 如b返回h
    if(pNode.right){
        let p = pNode.right;
        while(p.left){
            p = p.left;
        }
        return p;
    }
        
    // 程序走到这说明右子树不存在，如果pNode是其父节点的左节点，则返回其父节点     
    // 如d返回b
    if(pNode.next && pNode.next.left == pNode){
        return pNode.next;
    }
    
    // 程序走到这说明是根节点的左子树上的最右下角节点，则返回根节点
    // 如i返回a
    if(pNode.next){
        //判断是否是根节点左子树的最右边节点
        while(pNode.next && pNode.next.right == pNode){ 
            pNode = pNode.next;
        }
        return pNode.next;
    }
    return null;
}

二叉树测试用例编写

在做关于二叉树题目的时候想要验证自己写的程序是否是想要的结果时，需要写测试用例，但通常题目给我们的是数组，那么就需要利用层次遍历的思想，将数组转换成二叉树，然后将二叉树逐行或者按某种方式打印出来。

具体实现请参考二叉树的构造方法