NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树

NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树

搜索二叉树：

使用递归方式遍历如果该节点有左子树，则左子树上的所以值应当小于当前节点的值如果该节点有右子树，则由子树上的所以值应当大于当前节点的值也就是说中序遍历的结果应当是递增的

完全二叉树：

层次遍历情况下如果遇到了最后一个节点将 flag 为 true

左右孩子不全只有左孩子没有右孩子 如果在之前已经遇到最后一个节点的情况下,当前节点不是叶子结点，那么不是完全二叉树如果当前节点只有右孩子没有左孩子则不是完全二叉树

function judgeIt( root ) {
    var ansSearch = true
    var ansAll = true
//     标记是否遇到不全的节点
    var flag = false
//     当为空树或者只有一个节点时 直接返回
    if(!root || (root.left == null && root.right == null))
        return [ansSearch , ansAll]
    var pre  = null;
    function dfs(node){
        if(node == null) return;
        dfs(node.left)
        if(pre == null){
            pre = node.val
        }else{
            if(node.val < pre){
                ansSearch = false
            }
            pre = node.val
        }
        dfs(node.right)
    }
    dfs(root)
    var queue = [root]
    while(queue.length != 0){
        var font = queue.pop()
//        判断该节点是否符合完全二叉树
        if(flag && !(!font.left && !font.right)){
            ansAll = false
        }
        if(!font.left && font.right) ansAll = false
        if((!font.left && !font.right)||(font.left&&!font.right)){
            flag = true
        }
        
        if(font.left) queue.unshift(font.left)
        if(font.right) queue.unshift(font.right)
    }
    return [ansSearch , ansAll]
}
module.exports = {
    judgeIt : judgeIt
};