当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.965.Univalued Binary Tree 单值二叉树

LeetCode.965.Univalued Binary Tree 单值二叉树

题目描述

965 Univalued Binary Tree
https://leetcode-cn.com/problems/univalued-binary-tree/

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

Input: [1,1,1,1,1,null,1]

       1
      / \
    1    1
   / \    \
  1   1    1

Output: true

Example 2:

Input: [2,2,2,5,2]

       2
      / \
    2    2
   / \
  5   2
Output: false

Note:
The number of nodes in the given tree will be in the range [1, 100].
Each node’s value will be an integer in the range [0, 99].


解题过程

递归深度优先搜索dfs
递归函数返回子树root是否单值的
当root的左右子树都是单值的且根节点等于左右子树的值时,root是单值的
空树 null 是单值的
时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV2020 {
    public boolean isUnivalTree(TreeNode root) {
        if (null == root) {
            return true;
        }
        boolean res = true;
        if (null != root.left) {
            res = isUnivalTree(root.left) && root.val == root.left.val;
        }
        if (null != root.right) {
            res &= isUnivalTree(root.right) && root.val == root.right.val;
        }
        return res;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_965_UnivaluedBinaryTree.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_965_UnivaluedBinaryTree.java


上一篇 LeetCode.1022.Sum of Root To Leaf Binary Numbers 从根到叶的二进制数之和

下一篇 LeetCode.938.Range Sum of BST 二叉搜索树BST的范围和

阅读
评论
246
阅读预计1分钟
创建日期 2020-02-02
修改日期 2020-02-02
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论