LeetCode 965简单树 · BST

单值二叉树图解题解

这道题到底在问什么

给定二叉树 root。若树中每个节点的值都相同，返回 true，否则返回 false。节点数范围 [1, 100]，节点值范围 [0, 99]。

输入: root=[1,1,1,1,1,null,1]
输出: true（全是 1）
输入: root=[2,2,2,5,2]
输出: false（有个 5）

先想最直接的笨办法

先看全局。DFS 从根节点出发(紫色)，第一件事是把根的值记下来当基准:x 等于 7。之后每个节点都要和这个 7 去比。这棵树七个节点，我们按先序一个一个走。（动画第 4 步）

最优解：一步一步想明白

3记住这句「记下根值 x，每个节点都和 x 比，有一个不等就 false」，下面每一帧都在套它。
4基准 x = 7先看全局。DFS 从根节点出发(紫色)，第一件事是把根的值记下来当基准:x 等于 7。之后每个节点都要和这个 7 去比。这棵树七个节点，我们按先序一个一个走。
57 等于 7，匹配根自己当然等于基准 7，匹配通过，标绿。基准已经定好是 7，接下来轮到它的孩子们逐个来比。
6当前值 7DFS 先序走到根的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
77 等于 7，匹配根的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
8当前值 7DFS 先序走到左孩子的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
97 等于 7，匹配左孩子的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
10当前值 7DFS 先序走到左孩子的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
117 等于 7，匹配左孩子的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
12当前值 7DFS 先序走到根的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
137 等于 7，匹配根的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
14当前值 7DFS 先序走到右孩子的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
157 等于 7，匹配右孩子的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
16当前值 7DFS 先序走到右孩子的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
177 等于 7，匹配右孩子的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
18答案 true七个节点全部走完，每一个都等于基准 7，整棵树标绿。没有任何一个节点和根值不同，所以这是单值二叉树，返回 true。一遍 DFS 就把全体节点比完了。
19基准 x = 7基准根值 x = 7,已确认同值: 0 / 3
207 等于 7，匹配基准根值 x = 7,已确认同值: 1 / 3
21当前值 7基准根值 x = 7,已确认同值: 1 / 3
227 等于 7，匹配基准根值 x = 7,已确认同值: 2 / 3
23当前值 9基准根值 x = 7,已确认同值: 2 / 3
249 不等于 7基准根值 x = 7,发现不同值 9 ≠ 7
25答案 false判定: 存在不同值,结果 false

⚠️ 容易写错的地方

✗ 错：拿「当前节点和它的父节点」比

✓ 对：统一和「根值 x」比

和父比也对(相邻相等可推出全等)，但和固定的根值 x 比更直观、不易写错

✗ 错：空树或空子树当成 false

✓ 对：空子树应返回 true

没有节点就没有「不同值」，空子树天然满足条件，返回 true 才能让递归正确合并

✗ 错：发现不等还继续递归整棵树

✓ 对：发现不等立刻短路返回 false

靠 and 短路，第一个不等就停，避免无谓遍历

完整代码（Python / C++ / Java）

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);
    }
}

复杂度

时间

O(n)

最坏要访问每个节点各一次做一次比较，n 是节点总数;提前发现不等会更快返回

空间

O(h)

只用递归栈，深度等于树高 h;平衡时 O(log n)，退化成链时最坏 O(n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着单值二叉树的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

不用递归，能用 BFS 层序遍历做吗?+

可以。用一个队列做层序遍历:取出根值当基准 x，然后每弹出一个节点就比一次它的值是否等于 x，不等立刻返回 false;把非空孩子入队继续。所有节点都比完没发现不同就返回 true。和 DFS 复杂度一样，时间 O(n)、空间是队列宽度 O(n)。

为什么和「相邻父子比」也等价?+

如果每一对相邻的父子节点值都相等，那么沿任意路径从根走到任何节点，值都一路不变，于是全体节点都等于根值;反过来全体等于根值也意味着相邻父子必然相等。两种判法等价，和固定根值 x 比写起来更不容易出错。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把单值二叉树一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 965简单树 · BST

单值二叉树图解题解

这道题到底在问什么

给定二叉树 root。若树中每个节点的值都相同，返回 true，否则返回 false。节点数范围 [1, 100]，节点值范围 [0, 99]。

输入: root=[1,1,1,1,1,null,1]
输出: true（全是 1）
输入: root=[2,2,2,5,2]
输出: false（有个 5）

先想最直接的笨办法

最优解：一步一步想明白

3记住这句「记下根值 x，每个节点都和 x 比，有一个不等就 false」，下面每一帧都在套它。
4基准 x = 7先看全局。DFS 从根节点出发(紫色)，第一件事是把根的值记下来当基准:x 等于 7。之后每个节点都要和这个 7 去比。这棵树七个节点，我们按先序一个一个走。
57 等于 7，匹配根自己当然等于基准 7，匹配通过，标绿。基准已经定好是 7，接下来轮到它的孩子们逐个来比。
6当前值 7DFS 先序走到根的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
77 等于 7，匹配根的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
8当前值 7DFS 先序走到左孩子的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
97 等于 7，匹配左孩子的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
10当前值 7DFS 先序走到左孩子的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
117 等于 7，匹配左孩子的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
12当前值 7DFS 先序走到根的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
137 等于 7，匹配根的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
14当前值 7DFS 先序走到右孩子的左孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
157 等于 7，匹配右孩子的左孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
16当前值 7DFS 先序走到右孩子的右孩子(紫色)，它的值是 7。先别急着放过，按套路要拿它和基准根值 7 比一比，看是不是同一个值。
177 等于 7，匹配右孩子的右孩子的值 7 正好等于基准 7，匹配通过，标绿。到目前为止还没遇到不一样的，继续往下走。
18答案 true七个节点全部走完，每一个都等于基准 7，整棵树标绿。没有任何一个节点和根值不同，所以这是单值二叉树，返回 true。一遍 DFS 就把全体节点比完了。
19基准 x = 7基准根值 x = 7,已确认同值: 0 / 3
207 等于 7，匹配基准根值 x = 7,已确认同值: 1 / 3
21当前值 7基准根值 x = 7,已确认同值: 1 / 3
227 等于 7，匹配基准根值 x = 7,已确认同值: 2 / 3
23当前值 9基准根值 x = 7,已确认同值: 2 / 3
249 不等于 7基准根值 x = 7,发现不同值 9 ≠ 7
25答案 false判定: 存在不同值,结果 false

⚠️ 容易写错的地方

✗ 错：拿「当前节点和它的父节点」比

✓ 对：统一和「根值 x」比

和父比也对(相邻相等可推出全等)，但和固定的根值 x 比更直观、不易写错

✗ 错：空树或空子树当成 false

✓ 对：空子树应返回 true

没有节点就没有「不同值」，空子树天然满足条件，返回 true 才能让递归正确合并

✗ 错：发现不等还继续递归整棵树

✓ 对：发现不等立刻短路返回 false

靠 and 短路，第一个不等就停，避免无谓遍历

完整代码（Python / C++ / Java）

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);
    }
}

复杂度

时间

O(n)

最坏要访问每个节点各一次做一次比较，n 是节点总数;提前发现不等会更快返回

空间

O(h)

只用递归栈，深度等于树高 h;平衡时 O(log n)，退化成链时最坏 O(n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着单值二叉树的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

不用递归，能用 BFS 层序遍历做吗?+

为什么和「相邻父子比」也等价?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

单值二叉树 图解题解

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

单值二叉树 图解题解

这道题到底在问什么

先想最直接的笨办法

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

单值二叉树图解题解

单值二叉树图解题解