写点什么

【LeetCode】单值二叉树 Java 题解

作者:HQ数字卡
  • 2022 年 5 月 24 日
  • 本文字数:911 字

    阅读完需:约 3 分钟

题目描述

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


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


示例 1:
输入:[1,1,1,1,1,null,1]输出:true
示例 2:
输入:[2,2,2,5,2]输出:false

来源:力扣(LeetCode)链接:https://leetcode.cn/problems/univalued-binary-tree著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法题目是二叉树题目,二叉树是我们最常见的数据结构。我们处理二叉树题目,一般可以采用递归和遍历的方法解决。

  • 题目给定的单值二叉树,含义是二叉树每一个值都相等,我们需要遍历每一个二叉树的值,然后比较是否相等。我使用了队列这种数据结构,当找到第一个不相等的值的时候,返回 false。实现代码如下,供参考。

通过代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public boolean isUnivalTree(TreeNode root) {        boolean ans = true;        Queue<TreeNode> queue = new LinkedList<>();        int preVal = -1;        queue.offer(root);        while (!queue.isEmpty()) {            TreeNode current = queue.poll();            if (current != null) {                int currentVal = current.val;                if (preVal == -1) {                    preVal = currentVal;                } else if (preVal != currentVal) {                    ans = false;                    return ans;                }                queue.offer(current.left);                queue.offer(current.right);            }        }
return ans; }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n),空间复杂度是 O(n)

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 4
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】单值二叉树Java题解_LeetCode_HQ数字卡_InfoQ写作社区