深度解析：如何高效判断二叉树是否为单值树

在二叉树的众多有趣属性中，"单值树"（Univalued Binary Tree）是一个经常在面试和算法练习中遇到的概念。你是否想过如何快速验证一棵树中的每一个节点是否都存储着相同的数据？在这篇文章中，我们将深入探讨这个问题。我们将从基本概念入手，使用深度优先搜索（DFS）策略来解决问题，并通过详细的代码实现和案例分析，帮助你彻底掌握这一技巧。无论你是在准备技术面试，还是希望提升算法设计能力，这篇文章都将为你提供实用的见解和代码范例。

什么是单值树？

首先，让我们明确一下定义。所谓的单值树，是指二叉树中的每一个节点都存储着相同的值。这意味着，对于树中的任意节点，其值必须等于根节点的值，同时也必须等于其所有子节点的值。

为了更直观地理解，让我们看两个例子。

示例 1：单值树

输入：
      1
    /   \
   1     1
  / \     \
 1   1     1

输出： YES

解释： 在这棵树中，根节点的值是 1。通过观察，我们可以发现所有其他节点（无论是左子节点、右子节点还是叶子节点）的值也都是 1。因为没有任何节点的值与根节点不同，所以我们称这棵树是单值的，输出 "YES"。

示例 2：非单值树

输入：
      9
    /   \
   2     4
  / \     \
-1   3     0

输出： NO

解释： 在这里，根节点的值是 9，但其左子节点的值是 2。很明显，2 不等于 9。因此，这棵树不满足单值条件，我们输出 "NO"。实际上，只要树中存在任何一个节点的值与其他节点不同，它就不是单值树。

解题思路：深度优先搜索（DFS）

既然我们已经理解了问题的定义，那么如何用代码来实现它呢？最直观且高效的方法是使用深度优先搜索（DFS）。

我们的核心思路非常简单：

• 确定基准值：既然所有节点必须相同，那么我们可以直接取根节点的值作为基准（Reference Value）。
• 遍历与检查：遍历整棵树。在访问每一个节点时，将其值与根节点的值进行比较。
• 判断逻辑：

* 如果发现任何一个节点的值与根节点不同，立即停止遍历并返回 false（或 "NO"）。

* 如果遍历了所有节点都没有发现不匹配的情况，则返回 true（或 "YES"）。

使用 DFS（无论是前序、中序还是后序遍历）非常适合这里，因为我们需要深入到树的每一个角落去"检查"每一个节点。递归是 DFS 的天然实现方式，代码会非常简洁优雅。

算法实现细节

让我们深入探讨一下具体的算法逻辑。我们的函数 isUnivalTree 将接收树的根节点作为参数。

递归的三部曲

• 终止条件：

* 如果当前节点为空（INLINECODE40c6c02f），说明已经遍历到了树的末尾。空节点不影响单值性质，因此返回 INLINECODEbe82db61。

• 当前层逻辑：

* 检查当前节点的左子节点是否存在。如果存在，且其值与当前节点（也就是父节点）的值不同，则返回 false。

* 检查当前节点的右子节点是否存在。如果存在，且其值与当前节点不同，则返回 false。

注意：这一步其实就是将子节点的值与父节点（或者说根节点）进行对齐。*

• 递归调用：

* 如果当前节点的左右子节点值都匹配，那么我们需要继续向下检查。我们将递归调用 isUnivalTree 函数分别传入左子树和右子树。

* 只有当左子树和右子树都是单值树时，整棵树才是单值树。因此使用逻辑与（AND）连接递归结果。

这种"自顶向下"的检查方式非常高效，因为一旦在某一个分支发现不匹配，就会立即返回，不再继续遍历该分支的后续节点。

代码实现

接下来，让我们看看在不同编程语言中如何实现这个逻辑。我们将涵盖 C++、Java 和 Python3，并添加详细的中文注释，确保你能理解每一行代码的作用。

1. C++ 实现

C++ 提供了高性能的指针操作，非常适合处理树结构。

// C++ Program to check if a binary tree is univalued
#include 
using namespace std;

// 定义树节点的结构体
struct Node {
    int data;
    Node* left;
    Node* right;
};

// 辅助函数：创建一个新节点
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return (temp);
}

// 核心函数：检查树是否为单值树
bool isUnivalTree(Node* root)
{
    // 情况1：如果树是空的（或者递归到了叶子节点的下方），
    // 我们认为它满足条件。
    if (!root) {
        return true;
    }

    // 情况2：检查左子节点
    // 如果左子节点存在，且其值不等于根节点（父节点）的值
    // 则直接返回 false
    if (root->left != NULL
        && root->data != root->left->data)
        return false;

    // 情况3：检查右子节点
    // 如果右子节点存在，且其值不等于根节点（父节点）的值
    // 则直接返回 false
    if (root->right != NULL
        && root->data != root->right->data)
        return false;

    // 递归步骤：
    // 如果当前节点的直接子节点都匹配，
    // 我们继续检查左子树和右子树的内部结构。
    // 只有两者都返回 true，整棵树才是单值的。
    return isUnivalTree(root->left)
           && isUnivalTree(root->right);
}

// 主函数：驱动代码
int main()
{
    /*
        构建如下的单值二叉树：
            1
          /   \
         1     1
       /  \     \
      1    1     1
    */
    Node* root = newNode(1);
    root->left = newNode(1);
    root->right = newNode(1);
    root->left->left = newNode(1);
    root->left->right = newNode(1);
    root->right->right = newNode(1);

    // 调用函数并根据结果输出
    if (isUnivalTree(root)) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
    
    // 为了测试，你可以尝试修改上面的节点值，例如把某个节点改为2，看看输出是否变为 NO
    return 0;
}

2. Java 实现

Java 的实现方式与 C++ 非常相似，但我们需要注意对象的引用和空指针检查。

// Java Program to check if a binary tree is univalued
import java.util.*;

class GFG {

    // 定义树节点类
    static class Node {
        int data;
        Node left;
        Node right;
    };

    // 辅助函数：创建一个新节点
    static Node newNode(int data) {
        Node temp = new Node();
        temp.data = data;
        temp.left = temp.right = null;
        return (temp);
    }

    // 核心函数：检查树是否为单值树
    static boolean isUnivalTree(Node root) {
        // 基准情况：如果节点为空，返回 true
        if (root == null) {
            return true;
        }

        // 检查左子节点是否与当前节点值不同
        if (root.left != null
            && root.data != root.left.data)
            return false;

        // 检查右子节点是否与当前节点值不同
        if (root.right != null
            && root.data != root.right.data)
            return false;

        // 递归检查左右子树
        return isUnivalTree(root.left)
               && isUnivalTree(root.right);
    }

    // 主函数
    public static void main(String[] args) {
        /*
            构建如下的单值二叉树：
                1
              /   \
             1     1
           /  \     \
          1    1     1
        */
        Node root = newNode(1);
        root.left = newNode(1);
        root.right = newNode(1);
        root.left.left = newNode(1);
        root.left.right = newNode(1);
        root.right.right = newNode(1);

        if (isUnivalTree(root)) {
            System.out.print("YES");
        } else {
            System.out.print("NO");
        }
    }
}

3. Python3 实现

Python 的语法更加简洁，利用其灵活的变量声明可以快速构建树结构。

# Python3 Program to check if a binary tree is univalued

# 定义树节点类
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# 核心函数：检查树是否为单值树
def isUnivalTree(root):
    
    # 如果树为空（递归基准情况）
    if (not root):
        return True

    # 检查左子节点
    # 如果左子节点存在，且值不等于当前节点
    if (root.left != None and root.data != root.left.data):
        return False

    # 检查右子节点
    # 如果右子节点存在，且值不等于当前节点
    if (root.right != None and root.data != root.right.data):
        return False

    # 递归检查左右子树
    return isUnivalTree(root.left) and isUnivalTree(root.right)

# 主函数驱动代码
if __name__ == ‘__main__‘:
    """
    构建如下的单值二叉树：
          1
        /   \
       1     1
     /  \     \
    1    1     1
    """
    root = Node(1)
    root.left = Node(1)
    root.right = Node(1)
    root.left.left = Node(1)
    root.left.right = Node(1)
    root.right.right = Node(1)

    if (isUnivalTree(root)):
        print("YES")
    else:
        print("NO")

复杂度分析

作为专业的开发者，我们不仅要会写代码，还要懂得分析代码的性能。

• 时间复杂度：O(N)。其中 N 是二叉树中的节点数量。在最坏的情况下，我们需要访问树中的每一个节点才能确定它是否是单值的（例如，树确实是单值的，或者只有最后一个叶子节点不同）。因此，时间复杂度与节点数成线性关系。
• 空间复杂度：O(H)。这里 H 是树的高度。这是由于递归调用栈所消耗的空间。在最坏的情况下（树退化为链表），递归深度为 N，空间复杂度为 O(N)。在最好情况下（完全平衡树），高度为 log N，空间复杂度为 O(log N)。

实际应用场景与最佳实践

虽然 "单值树" 看起来像一个纯粹的算法练习题，但它在实际开发中也有隐喻意义。例如，在某些配置树或数据分类树中，我们可能需要验证某个分支下的所有配置项是否都属于同一类型或具有相同的权限等级。

常见错误提示

在编写这段代码时，新手容易犯以下几个错误：

• 空指针异常：在检查子节点之前，没有先判断子节点是否为 INLINECODEda63d2b2，直接访问 INLINECODE502c6bf8 会导致程序崩溃。务必先判断存在性，再判断值。
• 逻辑短路：在递归调用时，如果使用逻辑与（INLINECODE5885fc56 或 INLINECODEb70ca886），大部分语言会进行短路优化。这意味着如果左子树返回 false，右子树将不会被检查。这通常是好事（性能优化），但在某些需要记录所有错误节点的场景下，你可能需要不同的逻辑。

进阶思考

我们可以尝试另一种思路：带参数的 DFS。

目前的递归是比较"父节点"与"子节点"。另一种方法是：将根节点的值存储在一个变量中（或者作为递归函数的参数传递下去），然后在函数内部只检查当前节点的值是否等于那个传入的初始值。

逻辑如下：

• 记录 root_val = root->data。
• 定义函数 check(node, root_val)。
• 如果 node 为空，返回 true。
• 如果 node->data != root_val，返回 false。
• 否则，返回 check(node->left, root_val) && check(node->right, root_val)。

这种方法同样有效，且在某些情况下逻辑更直观（统一对标根节点），但需要额外的函数参数空间。

总结

在这篇文章中，我们深入探讨了如何判断一棵二叉树是否为单值树。我们使用了经典的深度优先搜索（DFS）方法，通过递归简洁地实现了这一逻辑。我们涵盖了从问题定义、算法思路、代码实现（C++, Java, Python）到复杂度分析的完整流程。

关键点在于：

• 利用递归的终止条件处理空节点。
• 在递归过程中实时比较当前节点与其子节点的值。
• 利用逻辑与确保所有分支都满足条件。

希望这篇文章对你有所帮助。下次当你面对二叉树遍历问题时，你能更加自信地运用递归这一强大的工具。如果你有任何疑问或想要探讨其他二叉树问题，欢迎继续交流。