LeetCode刷题【965】单值二叉树

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

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：

输入：[1,1,1,1,1,null,1]
输出：true

示例 2：

输入：[2,2,2,5,2]
输出：false

提示：

1. 给定树的节点数范围是 [1, 100]。
2. 每个节点的值都是整数，范围为 [0, 99] 。

题解

今天是继续练习二叉树相关的题目，深化学习掌握

本题是直观的二叉树遍历要求的题目，可以深搜也可以广搜，深搜每递进一层都需要开启一层额外的栈空间，最终和树的高度是相关的，广搜需要新建额外的队列保存下一层需要遍历的结果集。个人还是偏向深搜来解题一点。

多加个notSame值判断当前判断的情况，可以提前中断，如果有不同了，不用遍历完全树，后续其他节点也都不用再遍历了。当然如果是广搜的要实现提前中断就很容易了。直接终止while循环退出即可。

class Solution {
    boolean notSame = false;
    public boolean isUnivalTree(TreeNode root) {
        return isSameTree(root);
    }

    public boolean isSameTree(TreeNode root){
        if (notSame){
            return false;
        }
        if (root==null){
            return true;
        }
        if (root.left != null && root.left.val != root.val){
            notSame = true;
            return false;
        }
        if (root.right != null && root.right.val != root.val){
            notSame = true;
            return false;
        }
        if (isSameTree(root.left) && isSameTree(root.right)){
            return true;
        }
        notSame = true;
        return false;
    }

}