965.单值二叉树

发表于 | 分类于
字数统计: 259 | 阅读时长 ≈ 1

一、题目描述

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

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

示例 1：

binarysearchtree_improved.png

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

示例 2：

screen-shot-2018-12-25-at-50050-pm.png

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

提示：

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

二、题解

1.递归

1.1 思路

  1. 空树为单值二叉树
  2. 不是空树时，递归判断根节点的值与孩子节点是否相等
  3. 左右子树都相等时，返回true，否则返回false

1.2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool help(struct TreeNode *root, int val)
{
    if (root == NULL)
        return true;
    if (root->val == val)
        return help(root->left, val) && help(root->right, val);
    return false;
}

bool isUnivalTree(struct TreeNode *root)
{
    if (root == NULL)
        return true;
    int single = root->val;
    return help(root->left, single) && help(root->right, single);
}