如何验证二叉树有效性？给定根节点的合法二叉树校验

嘿，我来帮你搞定这个验证有效二叉树的问题！首先得明确啥是有效二叉树——咱要的不是二叉搜索树（BST），就是最基础的二叉树定义：

• 每个节点最多只能有两个子节点（左子节点、右子节点，空节点不算）
• 绝对不能有节点被多个父节点指向（比如一个节点同时是两个不同节点的孩子）
• 不能有循环引用（比如子节点直接/间接指向父节点）

你给的合法示例完全符合这些规则，每个节点最多俩孩子，也没有重复指向；而非法示例应该是存在某个节点被两个父节点引用（比如X3同时是X4的右孩子和X5的左孩子），这就直接违反了规则。

实现思路 #

我推荐用**深度优先搜索（DFS）**来遍历整棵树，同时记录已经访问过的节点：

1. 每访问一个节点，先检查它的非空孩子数量有没有超过2——超过的话直接判定无效
2. 然后看这个节点是不是已经被访问过了，如果是，说明要么有循环，要么有重复父节点，直接返回False
3. 递归检查左右子树，全通过的话就返回True

Python 代码实现 #

首先先补全你写了一半的Node类：

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

然后是核心的验证函数：

def is_valid_binary_tree(root):
    visited = set()
    
    def dfs(node):
        if not node:
            return True
        # 要是这个节点已经来过，说明有问题
        if node in visited:
            return False
        visited.add(node)
        # 统计非空的子节点数量，最多只能有2个
        non_empty_children = 0
        if node.left:
            non_empty_children += 1
        if node.right:
            non_empty_children += 1
        if non_empty_children > 2:
            return False
        # 递归检查左右子树，必须都合法
        return dfs(node.left) and dfs(node.right)
    
    # 空树也算是有效的二叉树哦
    return dfs(root) if root else True

测试一下你的示例 #

我们用你给的例子来验证代码：

合法树测试

# 构建你说的合法树：
# X1
# /  \
# X4  X5
# \    \
# X3    X7
x3 = Node("X3")
x7 = Node("X7")
x4 = Node("X4", right=x3)
x5 = Node("X5", right=x7)
root_valid = Node("X1", x4, x5)
print(is_valid_binary_tree(root_valid))  # 输出: True

非法树测试

# 构建你说的非法树（这里假设X3同时是X4的右孩子和X5的左孩子）：
# X1
# /  \
# X4  X5
# \  /
# X3 X3
x3 = Node("X3")
x4 = Node("X4", right=x3)
x5 = Node("X5", left=x3)
root_invalid = Node("X1", x4, x5)
print(is_valid_binary_tree(root_invalid))  # 输出: False

额外说明 #

• 要是输入的根节点是None（空树），我们默认它是有效的，这是行业内的常规定义
• 这个方法的效率很高，时间复杂度是O(n)（每个节点只走一遍），空间复杂度也是O(n)（最坏情况比如链状树，递归栈或者visited集合要存所有节点）

内容的提问来源于stack exchange，提问作者John Doe