965. Univalued Binary Tree
Approach
DFS; return false if any node's value differs from its parent or if any child subtree is not univalued.
Key Techniques
Tree problems typically require recursive DFS or iterative BFS. Common patterns: preorder for serialization, inorder for BST sorted output, postorder for bottom-up aggregation. Always consider edge cases: null nodes, single-node trees, and skewed (list-like) trees.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
// Approach: DFS; return false if any node's value differs from its parent or if any child subtree is not univalued.
// Time: O(n) Space: O(n)
public class TreeNode(TreeNode root)
{
if (root == null)
return true;
if (root.left != null && root.left.val != root.val)
return false;
if (root.right != null && root.right.val != root.val)
return false;
return IsUnivalTree(root.left) && IsUnivalTree(root.right);
}
}