题目描述
思路解析
一句话答案：LeetCode 965 单值二叉树：判断是不是每个节点的值都相同，记下根值 x 做一次 DFS，逐点和 x 比、有一个不等就短路返回 false，时间 O(n)、空间 O(h)。
每个节点的值都相同吗，返回什么
给一棵二叉树 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)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句「记下根值 x，每个节点都和 x 比，有一个不等就 false」，下面每一帧都在套它。
准备 · 记下根值 x：先看全局。DFS 从根节点出发(紫色)，第一件事是把根的值记下来当基准:x 等于 7。之后每个节点都要和这个 7 去比。这棵树七个节点，我们按先序一个一个走。
根 · 等于 x：根自己当然等于基准 7，匹配通过，标绿。基准已经定好是 7，接下来轮到它的孩子们逐个来比。
走到 · 根的左孩子：DFS 先序走到根的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
根的左孩子 · 等于 x：根的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
走到 · 左孩子的左孩子：DFS 先序走到左孩子的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
左孩子的左孩子 · 等于 x：左孩子的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
走到 · 左孩子的右孩子：DFS 先序走到左孩子的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
左孩子的右孩子 · 等于 x：左孩子的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
走到 · 根的右孩子：DFS 先序走到根的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
根的右孩子 · 等于 x：根的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
走到 · 右孩子的左孩子：DFS 先序走到右孩子的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
右孩子的左孩子 · 等于 x：右孩子的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
走到 · 右孩子的右孩子：DFS 先序走到右孩子的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
右孩子的右孩子 · 等于 x：右孩子的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
完成 · 全部同值：七个节点全部走完，每一个都等于基准 7，整棵树标绿。没有任何一个节点和根值不同，所以这是单值二叉树，返回 true。一遍 DFS 就把全体节点比完了。
反例 · 记下根值 x：换一棵反例树看 false 是怎么出来的。这棵只有三个节点，右孩子藏了个 9。同样先从根出发(紫色)，记下基准 x 等于 7。
根 · 等于 x：根的值 7 等于基准 7，匹配，标绿。继续按先序往左孩子走。
走到 · 根的左孩子：走到根的左孩子(紫色)，值是 7。拿它和基准 7 比。
根的左孩子 · 等于 x：左孩子的值 7 也等于基准 7，匹配，标绿。目前都很顺，接着走到右孩子。
走到 · 根的右孩子：走到根的右孩子(紫色)，它的值是 9。还是老规矩，拿 9 和基准根值 7 比一比。
右孩子 · 不等于 x：关键一帧:右孩子的值 9 不等于基准 7，比对失败，这个节点标红。出现了和根值不一样的节点。
反例 · 返回 false：只要有一个节点不等于基准，整棵树就不是单值树。这里 9 不等于 7，直接返回 false，剩下的节点都不用再看，这就是「发现不等立刻短路」。
单节点一定 true;全同 true;只要有一个值不同就 false。注意节点值可以是 0，0 也算正常值。
面试可补充 BFS 写法，以及「和根比」与「和父比」两种判法的等价性。
参考代码
from __future__ import annotationsfrom 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 = rightclass 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 = rightclass 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)复杂度
- 时间：O(n)，最坏要访问每个节点各一次做一次比较，n 是节点总数;提前发现不等会更快返回
- 空间：O(h)，只用递归栈，深度等于树高 h;平衡时 O(log n)，退化成链时最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问不用递归，能用 BFS 层序遍历做吗?
追问为什么和「相邻父子比」也等价?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从根到叶的二进制数之和
LeetCode 1022 · 简单 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题