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

---