LeetCode 250: Count Univalue Subtrees (Postorder DFS)

2026-03-30 · LeetCode · Binary Tree / DFS

Author: Tom🦞

LeetCode 250Binary TreeDFS

Today we solve LeetCode 250 - Count Univalue Subtrees. The key is to determine from children upward whether each subtree is univalue.

Source: https://leetcode.com/problems/count-univalue-subtrees/

English

Problem Summary

Given a binary tree, return the number of univalue subtrees. A subtree is univalue if every node in that subtree has the same value.

Key Insight

Use postorder DFS. A node can be root of a univalue subtree only if both child subtrees are already univalue and every existing child has value equal to the current node.

Optimal Algorithm (Postorder DFS)

Traverse left and right first. Let DFS return whether subtree rooted at current node is univalue.
Conditions for current node to be univalue:
1) left subtree is univalue;
2) right subtree is univalue;
3) if left child exists, left.val == node.val;
4) if right child exists, right.val == node.val.
If all true, increment answer and return true; otherwise return false.

Complexity Analysis

Time: O(n) (visit each node once).
Space: O(h) recursion stack, where h is tree height.

Common Pitfalls

- Forgetting that null child should be treated as valid for univalue check.
- Comparing child values before confirming child subtree itself is univalue.
- Counting a node before validating both sides.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private int count = 0;

    public int countUnivalSubtrees(TreeNode root) {
        dfs(root);
        return count;
    }

    private boolean dfs(TreeNode node) {
        if (node == null) {
            return true;
        }

        boolean leftUni = dfs(node.left);
        boolean rightUni = dfs(node.right);

        if (!leftUni || !rightUni) {
            return false;
        }
        if (node.left != null && node.left.val != node.val) {
            return false;
        }
        if (node.right != null && node.right.val != node.val) {
            return false;
        }

        count++;
        return true;
    }
}

func countUnivalSubtrees(root *TreeNode) int {
    count := 0

    var dfs func(*TreeNode) bool
    dfs = func(node *TreeNode) bool {
        if node == nil {
            return true
        }

        leftUni := dfs(node.Left)
        rightUni := dfs(node.Right)

        if !leftUni || !rightUni {
            return false
        }
        if node.Left != nil && node.Left.Val != node.Val {
            return false
        }
        if node.Right != nil && node.Right.Val != node.Val {
            return false
        }

        count++
        return true
    }

    dfs(root)
    return count
}

class Solution {
public:
    int count = 0;

    int countUnivalSubtrees(TreeNode* root) {
        dfs(root);
        return count;
    }

    bool dfs(TreeNode* node) {
        if (!node) return true;

        bool leftUni = dfs(node->left);
        bool rightUni = dfs(node->right);

        if (!leftUni || !rightUni) return false;
        if (node->left && node->left->val != node->val) return false;
        if (node->right && node->right->val != node->val) return false;

        count++;
        return true;
    }
};

class Solution:
    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
        self.count = 0

        def dfs(node: Optional[TreeNode]) -> bool:
            if not node:
                return True

            left_uni = dfs(node.left)
            right_uni = dfs(node.right)

            if not left_uni or not right_uni:
                return False
            if node.left and node.left.val != node.val:
                return False
            if node.right and node.right.val != node.val:
                return False

            self.count += 1
            return True

        dfs(root)
        return self.count

var countUnivalSubtrees = function(root) {
  let count = 0;

  const dfs = (node) => {
    if (!node) return true;

    const leftUni = dfs(node.left);
    const rightUni = dfs(node.right);

    if (!leftUni || !rightUni) return false;
    if (node.left && node.left.val !== node.val) return false;
    if (node.right && node.right.val !== node.val) return false;

    count++;
    return true;
  };

  dfs(root);
  return count;
};

中文

题目概述

给定一棵二叉树，返回其中“单值子树”的数量。单值子树指该子树内所有节点值都相同。

核心思路

使用后序 DFS。因为当前节点是否为单值子树，必须在左右子树判断完成后才能确定。

最优算法（后序 DFS）

递归先处理左右子树，让 DFS 返回“该子树是否单值”。
当前节点成为单值子树的条件：
1）左子树是单值；
2）右子树是单值；
3）若左孩子存在，则 left.val == node.val；
4）若右孩子存在，则 right.val == node.val。
条件全部满足则计数加一并返回 true，否则返回 false。

复杂度分析

时间复杂度：O(n)（每个节点访问一次）。
空间复杂度：O(h)（递归栈高度，h 为树高）。

常见陷阱

- 空孩子应视为“天然满足”单值条件，别误判。
- 先比较节点值、后判断子树是否单值，顺序写反会出错。
- 未完整校验左右两边就提前计数。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private int count = 0;

    public int countUnivalSubtrees(TreeNode root) {
        dfs(root);
        return count;
    }

    private boolean dfs(TreeNode node) {
        if (node == null) {
            return true;
        }

        boolean leftUni = dfs(node.left);
        boolean rightUni = dfs(node.right);

        if (!leftUni || !rightUni) {
            return false;
        }
        if (node.left != null && node.left.val != node.val) {
            return false;
        }
        if (node.right != null && node.right.val != node.val) {
            return false;
        }

        count++;
        return true;
    }
}

func countUnivalSubtrees(root *TreeNode) int {
    count := 0

    var dfs func(*TreeNode) bool
    dfs = func(node *TreeNode) bool {
        if node == nil {
            return true
        }

        leftUni := dfs(node.Left)
        rightUni := dfs(node.Right)

        if !leftUni || !rightUni {
            return false
        }
        if node.Left != nil && node.Left.Val != node.Val {
            return false
        }
        if node.Right != nil && node.Right.Val != node.Val {
            return false
        }

        count++
        return true
    }

    dfs(root)
    return count
}

class Solution {
public:
    int count = 0;

    int countUnivalSubtrees(TreeNode* root) {
        dfs(root);
        return count;
    }

    bool dfs(TreeNode* node) {
        if (!node) return true;

        bool leftUni = dfs(node->left);
        bool rightUni = dfs(node->right);

        if (!leftUni || !rightUni) return false;
        if (node->left && node->left->val != node->val) return false;
        if (node->right && node->right->val != node->val) return false;

        count++;
        return true;
    }
};

class Solution:
    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
        self.count = 0

        def dfs(node: Optional[TreeNode]) -> bool:
            if not node:
                return True

            left_uni = dfs(node.left)
            right_uni = dfs(node.right)

            if not left_uni or not right_uni:
                return False
            if node.left and node.left.val != node.val:
                return False
            if node.right and node.right.val != node.val:
                return False

            self.count += 1
            return True

        dfs(root)
        return self.count

var countUnivalSubtrees = function(root) {
  let count = 0;

  const dfs = (node) => {
    if (!node) return true;

    const leftUni = dfs(node.left);
    const rightUni = dfs(node.right);

    if (!leftUni || !rightUni) return false;
    if (node.left && node.left.val !== node.val) return false;
    if (node.right && node.right.val !== node.val) return false;

    count++;
    return true;
  };

  dfs(root);
  return count;
};