[leetcode javascript]965. 单值二叉树

965. 单值二叉树

 

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时,才返回 true;否则返回 false

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
// 方法一
var isUnivalTree = function(root) {
    // if(!root)return true;//①这句不行
    // if(!root.left || !root.right)return true;//②这句不行
    // let left = (root.val == root.left.val && isUnivalTree(root.left));//③
    // let right = (root.val == root.right.val && isUnivalTree(root.right));//④
    let left = (root.left == null || (root.val == root.left.val && isUnivalTree(root.left)));
    let right = (root.right == null || (root.val == root.right.val && isUnivalTree(root.right)));

    return left && right;
};

突然觉得,递归是为了访问下面的节点。而递归结束条件是为了能回来。

①③④中:①会出错,因为下面有root.val == root.left.val的判断。比如root的左结点为空,进行root.val == root.left.val时因为root.left为空,调用它的值会直接报错

②③④中:②也不行,是运行结果出错。例子:

 

// 方法二 
// 先遍历二叉树取得每个结点的值,然后放入set中,若为单值二叉树,则set容器的大小一定为1
let tree = new Set();
var isUnivalTree = function(root) {
    if(!root)return 0; //①
    tree.add(root.val);
    isUnivalTree(root.left);
    isUnivalTree(root.right);
    if(tree.size > 1)return false;
    else return true;
}

①:return 0不太懂。而且无论改成return true或者return false都没错

// 方法三 利用bfs
var isUnivalTree = function(root) {
    const queue = [root];
    const equal = root.val;
    while(queue.length){
        const current = queue.shift();
        if(!current)continue;
        if(current.val !== equal)return false;
        queue.push(current.left, current.right);
    }
    return true;
}

 


版权声明:本文为weixin_40836227原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。