单值二叉树 图解题解

每个节点的值都相同吗，返回什么

给一棵二叉树 root，判断它是不是单值二叉树，也就是所有节点的值都一模一样。全都相同返回 true，只要冒出一个不同的就返回 false。题面例子 root=[1,1,1,1,1,null,1] 里各个位置的值全是 1，返回 true；root=[2,2,2,5,2] 中间混进一个 5，返回 false。节点数最多 100，值在 0 到 99 之间。

拿每个节点和父亲比，哪里别扭

一个想法是让每个节点和它的父节点比，只要相邻的父子处处相等，整棵树自然也就处处相等。这个判法本身没错，可写起来要一路把父节点的值当参数传下去，根节点又没有父亲、得单独开个头，这些边界很容易写岔。既然所有节点最终都要等于同一个值，不如挑一个固定的基准，让大家都跟它比。

干脆让所有节点都和根值 x 比

这个固定基准选根节点的值最省心，记成 x。之后不管走到哪个节点，都只和这个 x 比一次：等于就放行，不等就说明整棵树已经不是单值的了，直接返回 false，剩下的节点都不必再看。这样每个节点只关心自己和 x 的关系，不用惦记父亲是谁，边界一下子清爽了。遍历用 DFS，也就是顺着一条路一直走到底再回头。

一次 DFS 怎么逐点比、遇到不等就停

递归函数 dfs 收到一个节点：空节点直接返回 true，因为没有节点就谈不上有不同的值，空子树天然满足条件。非空时要三件事同时成立——当前节点值等于 x、左子树全等、右子树全等，用 and 串起来。and 带短路：当前值就不等于 x 时，后面两个递归压根不会执行；某棵子树返回了 false，也会立刻往上冒，不会再白跑剩下的节点。最外层先取 x=root.val，再从根调用 dfs。

全 1 的树和混进 5 的那棵各走几步

先看第一棵，x=1。从根开始，根值 1 等于 x，往下比左孩子 1、右孩子 1，再比下一层的几个 1，七个位置一路全等，最后返回 true。

再看第二棵，x=2。根值 2 对上 x，进入左孩子 2 也对上，接着比左孩子的左孩子，它的值是 5，5 不等于 2，这一层的 dfs 立刻返回 false。这个 false 顺着 and 一层层往上传，右边那半棵树根本没被碰过，最终返回 false。

空子树要返回 true，别把它写成 false

空节点的返回值是这里的坑点：把空子树当成 false，那么只要某个节点缺一个孩子，整棵树就会被误判成非单值。空子树没有任何节点，不存在「不同的值」，返回 true 才能让上层的 and 正确合并。还得记得，发现不等之后别再坚持把整棵树遍历完、白白多走一圈，靠 and 短路第一时间收手就好。时间上最坏要访问每个节点各比一次，O(n)；空间是递归栈的深度，等于树高 h，平衡时 O(log n)、退化成一条链时 O(n)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        def dfs(root: Optional[TreeNode]) -> bool:
            if root is None:
                return True
            return root.val == x and dfs(root.left) and dfs(root.right)

        x = root.val
        return dfs(root)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        int x = root->val;
        function<bool(TreeNode*)> dfs = [&]( TreeNode* root ) -> bool {
            if (!root) {
                return true;
            }
            return root->val == x && dfs(root->left) && dfs(root->right);
        };
        return dfs(root);
    }
};

Java

import java.util.*;
/**
 * 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 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 ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int x;

    public boolean isUnivalTree(TreeNode root) {
        x = root.val;
        return dfs(root);
    }

    private boolean dfs(TreeNode root) {
        if (root == null) {
            return true;
        }
        return root.val == x && dfs(root.left) && dfs(root.right);
    }
}