LeetCode 965: Univalued Binary Tree (DFS Value Consistency Check)
LeetCode 965TreeDFSToday we solve LeetCode 965 - Univalued Binary Tree.
Source: https://leetcode.com/problems/univalued-binary-tree/
English
Problem Summary
Given the root of a binary tree, return true if every node has the same value. Otherwise return false.
Key Insight
Use the root value as the invariant. During traversal, every visited node must match this target value.
Brute Force and Limitations
Collect all values into an array/set, then check if only one unique value exists. This works, but it uses extra memory and cannot early-stop as cleanly.
Optimal Algorithm Steps
1) Store root.val as target.
2) DFS each node.
3) If current value differs from target, return false immediately.
4) Both subtrees must be true.
Complexity Analysis
Let n be number of nodes.
Time: O(n).
Space: O(h) recursion stack, where h is tree height.
Common Pitfalls
- Forgetting null nodes should return true.
- Not short-circuiting on mismatch.
- Comparing children only to parent, but not consistently to root target.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* 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 Solution {
public boolean isUnivalTree(TreeNode root) {
return dfs(root, root.val);
}
private boolean dfs(TreeNode node, int target) {
if (node == null) return true;
if (node.val != target) return false;
return dfs(node.left, target) && dfs(node.right, target);
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isUnivalTree(root *TreeNode) bool {
target := root.Val
var dfs func(*TreeNode) bool
dfs = func(node *TreeNode) bool {
if node == nil {
return true
}
if node.Val != target {
return false
}
return dfs(node.Left) && dfs(node.Right)
}
return dfs(root)
}/**
* 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 target = root->val;
return dfs(root, target);
}
private:
bool dfs(TreeNode* node, int target) {
if (node == nullptr) return true;
if (node->val != target) return false;
return dfs(node->left, target) && dfs(node->right, target);
}
};# 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:
target = root.val
def dfs(node: Optional[TreeNode]) -> bool:
if node is None:
return True
if node.val != target:
return False
return dfs(node.left) and dfs(node.right)
return dfs(root)/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isUnivalTree = function(root) {
const target = root.val;
const dfs = (node) => {
if (node === null) return true;
if (node.val !== target) return false;
return dfs(node.left) && dfs(node.right);
};
return dfs(root);
};中文
题目概述
给定一棵二叉树根节点，若所有节点值都相同返回 true，否则返回 false。
核心思路
把根节点值作为目标值，遍历过程中每个节点都必须等于这个目标值，任何一次不等即可直接失败。
暴力解法与不足
可以先遍历收集所有节点值，再判断去重后是否只剩一种值。该方法可行，但额外占用空间，且不如 DFS 短路判断高效。
最优算法步骤
1）记录根节点值 target。
2）DFS 遍历整棵树。
3）若当前节点值不等于 target，立即返回 false。
4）左右子树都为 true 时整体才为 true。
复杂度分析
设节点总数为 n。
时间复杂度：O(n)。
空间复杂度：O(h)（递归栈高度，h 为树高）。
常见陷阱
- 空节点应返回 true。
- 发现不匹配后没有及时短路。
- 只与父节点比较，没有统一与根值进行一致性校验。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* 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 Solution {
public boolean isUnivalTree(TreeNode root) {
return dfs(root, root.val);
}
private boolean dfs(TreeNode node, int target) {
if (node == null) return true;
if (node.val != target) return false;
return dfs(node.left, target) && dfs(node.right, target);
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isUnivalTree(root *TreeNode) bool {
target := root.Val
var dfs func(*TreeNode) bool
dfs = func(node *TreeNode) bool {
if node == nil {
return true
}
if node.Val != target {
return false
}
return dfs(node.Left) && dfs(node.Right)
}
return dfs(root)
}/**
* 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 target = root->val;
return dfs(root, target);
}
private:
bool dfs(TreeNode* node, int target) {
if (node == nullptr) return true;
if (node->val != target) return false;
return dfs(node->left, target) && dfs(node->right, target);
}
};# 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:
target = root.val
def dfs(node: Optional[TreeNode]) -> bool:
if node is None:
return True
if node.val != target:
return False
return dfs(node.left) and dfs(node.right)
return dfs(root)/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isUnivalTree = function(root) {
const target = root.val;
const dfs = (node) => {
if (node === null) return true;
if (node.val !== target) return false;
return dfs(node.left) && dfs(node.right);
};
return dfs(root);
};
Comments