LeetCode 1361. 验证二叉树
字数 3208 2025-12-24 22:29:58

LeetCode 1361. 验证二叉树

题目描述

二叉树上有 n 个节点，编号从 0 到 n-1。我们用一个长度为 n 的整数数组 leftChild 和一个长度为 n 的整数数组 rightChild 来表示这棵树，其中：

  • leftChild[i] 表示节点 i 的左子节点编号。如果 i 没有左子节点，则 leftChild[i] = -1。
  • rightChild[i] 表示节点 i 的右子节点编号。如果 i 没有右子节点，则 rightChild[i] = -1。

你需要验证输入的这两个数组是否构成一棵有效的二叉树。一棵有效的二叉树必须满足：

  1. 所有节点有且只有一个父节点，除了根节点（根节点没有父节点）。
  2. 树中不存在环。
  3. 所有节点必须是连通的（即从根节点出发，可以到达所有节点）。

解题思路

这道题的关键是识别出二叉树的根节点，并从它开始验证结构的合法性。我们可以将其分解为以下几个步骤：

  1. 寻找根节点：根据定义，根节点是所有节点中，唯一一个没有父节点的节点。我们可以通过遍历 leftChild 和 rightChild 数组，记录每个节点是否有父节点。最后，那个没有被任何节点指向（即没有父节点）的节点，就是候选的根节点。注意，如果找到了多个这样的节点，说明结构分散成了多棵树，不符合“所有节点连通”的条件，因此是无效的。

  2. 深度优先搜索（DFS）验证：一旦我们确定了候选的根节点，就可以从它开始，进行深度优先搜索（或广度优先搜索），来验证剩下的两个条件：无环和全连通。

    • 无环检查：在DFS过程中，我们访问一个节点时，就将其标记为“正在访问”或“已访问”。如果我们在探索过程中，遇到了一个“正在访问”的节点，说明存在环。为了避免重复访问导致无限循环，当我们探索完一个节点的所有后代后，将其标记为“已访问”，这样下次再遇到它就知道是合法的重复引用（虽然二叉树结构不允许一个节点有多个父节点，但DFS的防重逻辑能帮助检查环）。
    • 全连通检查：在DFS过程中，我们记录访问到了多少个节点。最终，如果访问到的节点数等于总节点数 n，说明从根节点出发可以到达所有节点，即全连通；否则，说明存在无法从根节点到达的节点，结构无效。

  3. 数据结构：我们需要一个数据结构来记录每个节点的状态（未访问、正在访问、已访问），以及一个变量来记录每个节点是否有父节点。

解题步骤详解

我们按照上面的思路，一步一步来实现：

步骤 1：初始化与寻找根节点

  • 给定 n 个节点，编号从 0 到 n-1。
  • 我们创建一个布尔数组 hasParent，长度为 n，初始值全为 false，表示每个节点初始时都没有父节点。
  • 遍历 leftChild 和 rightChild 数组：
    • 对于 leftChild[i]，如果它的值不为 -1，则将 hasParent[leftChild[i]] 标记为 true，表示这个左子节点有了父节点 i。
    • 对于 rightChild[i]，做同样的处理。
  • 遍历结束后，检查 hasParent 数组。理论上，一棵有效的二叉树应该有且仅有一个节点的 hasParent 值为 false，这个节点就是根节点。如果 hasParent 数组中 false 的个数不为 1，说明要么没有根（每个节点都有父节点，形成了环），要么有多个根（森林），都直接返回 false。

步骤 2：从根节点开始深度优先搜索

  • 假设我们找到了一个候选根节点 root。
  • 我们创建一个整数数组 visited，长度为 n，用来标记每个节点的状态。我们可以用 0 表示“未访问”，1 表示“正在访问”（在本次DFS的递归栈中），2 表示“已访问”（已从递归栈中弹出，其所有后代都已处理完毕）。
  • 我们从 root 开始，进行DFS。DFS函数 dfs(node) 的逻辑如下：
    1. 首先检查当前节点 node 的状态：
      • 如果 visited[node] == 1，说明我们在同一条DFS路径上又遇到了这个节点，这表示存在环，立即返回 false。
      • 如果 visited[node] == 2，说明这个节点及其后代已经被完整探索过，为了避免重复工作，直接返回 true。
    2. 将当前节点状态标记为 1（正在访问）。
    3. 递归地探索左子节点和右子节点：
      • 如果 leftChild[node] != -1，则递归调用 dfs(leftChild[node])。如果递归返回 false，说明在左子树中发现了问题（环或不连通），本层也直接返回 false。
      • 对右子节点 rightChild[node] 做同样的处理。
    4. 探索完所有子节点后，将当前节点状态标记为 2（已访问）。
    5. 如果整个过程没有提前返回 false，说明从当前节点 node 开始的子树是有效的，返回 true。

步骤 3：检查连通性

  • 在调用完从根节点开始的DFS后，我们需要检查是否所有节点都被访问过。
  • 遍历 visited 数组，检查是否所有节点的状态都是 2（已访问）。如果不是，说明有节点无法从根节点到达，结构不连通，返回 false。
  • 如果所有节点都是 2，则说明这是一棵有效的二叉树，返回 true。

图解与边界条件

  • 示例1（有效）：

    • n = 4
    • leftChild = [1, -1, 3, -1]
    • rightChild = [2, -1, -1, -1]
    • 结构：节点0是根，左子为1，右子为2；节点1的左子为3。
    • 步骤1：hasParent 数组为 [false, true, true, true]，只有节点0无父节点，是根。
    • 步骤2：从节点0开始DFS，访问顺序0->1->3->2。所有节点状态变为2，无环。
    • 步骤3：所有节点已访问。返回 true。

  • 示例2（有环，无效）：

    • n = 4
    • leftChild = [1, -1, 3, -1]
    • rightChild = [2, 3, -1, -1]
    • 结构：节点0（根）的右子2的左子是3，但节点3又同时是节点0的左子1的右子？实际上，这会导致节点3有两个父节点（1和2），这首先违反了“每个节点只有一个父节点”的规则。在我们的算法中，hasParent[3] 会被设为 true 两次，但这不是关键。关键是在DFS中，当从节点0探索左子树（节点1）和右子树（节点2）时，节点3会被访问两次。如果第一次访问（从节点1）将其标记为2，第二次访问（从节点2）发现它是2，会直接返回true，不会报错。但我们需要在步骤1中就通过hasParent检查来防止这种情况。更复杂的环，比如节点0的左子指向节点1，节点1的右子指向节点0，我们的DFS在探索节点0时，会进入节点1，又从节点1回到节点0，此时节点0的状态是1（正在访问），从而检测到环并返回false。

  • 边界条件：

    • n = 1, leftChild = [-1], rightChild = [-1]。单个节点，是有效的二叉树。hasParent[0]=false，是根。DFS访问它，然后检查所有节点已访问。返回 true。
    • n = 0， 但题目中 n >= 1，所以不用特殊处理。

总结

这道题将二叉树结构的验证转化为了图的遍历问题。通过统计入度（父节点数）找到唯一的根节点，然后通过带有状态标记的深度优先搜索来检查从该根节点出发，图中是否存在环以及是否所有节点都能被访问到。这是一种非常经典的、结合了拓扑排序思想和图遍历思想的解法。

LeetCode 1361. 验证二叉树 题目描述 二叉树上有 n 个节点，编号从 0 到 n-1 。我们用一个长度为 n 的整数数组 leftChild 和一个长度为 n 的整数数组 rightChild 来表示这棵树，其中： leftChild[i] 表示节点 i 的左子节点编号。如果 i 没有左子节点，则 leftChild[i] = -1 。 rightChild[i] 表示节点 i 的右子节点编号。如果 i 没有右子节点，则 rightChild[i] = -1 。 你需要验证输入的这两个数组是否构成一棵 有效的二叉树 。一棵有效的二叉树必须满足： 所有节点有且只有一个父节点， 除了根节点 （根节点没有父节点）。 树中不存在环。 所有节点必须是连通的（即从根节点出发，可以到达所有节点）。 解题思路 这道题的关键是识别出二叉树的 根节点 ，并从它开始验证结构的合法性。我们可以将其分解为以下几个步骤： 寻找根节点 ：根据定义，根节点是所有节点中，唯一一个 没有父节点 的节点。我们可以通过遍历 leftChild 和 rightChild 数组，记录每个节点是否有父节点。最后，那个没有被任何节点指向（即没有父节点）的节点，就是候选的根节点。注意，如果找到了多个这样的节点，说明结构分散成了多棵树，不符合“所有节点连通”的条件，因此是无效的。 深度优先搜索（DFS）验证 ：一旦我们确定了候选的根节点，就可以从它开始，进行深度优先搜索（或广度优先搜索），来验证剩下的两个条件：无环和全连通。 无环检查 ：在DFS过程中，我们访问一个节点时，就将其标记为“正在访问”或“已访问”。如果我们在探索过程中，遇到了一个“正在访问”的节点，说明存在环。为了避免重复访问导致无限循环，当我们探索完一个节点的所有后代后，将其标记为“已访问”，这样下次再遇到它就知道是合法的重复引用（虽然二叉树结构不允许一个节点有多个父节点，但DFS的防重逻辑能帮助检查环）。 全连通检查 ：在DFS过程中，我们记录访问到了多少个节点。最终，如果访问到的节点数等于总节点数 n ，说明从根节点出发可以到达所有节点，即全连通；否则，说明存在无法从根节点到达的节点，结构无效。 数据结构 ：我们需要一个数据结构来记录每个节点的状态（未访问、正在访问、已访问），以及一个变量来记录每个节点是否有父节点。 解题步骤详解 我们按照上面的思路，一步一步来实现： 步骤 1：初始化与寻找根节点 给定 n 个节点，编号从 0 到 n-1。 我们创建一个布尔数组 hasParent ，长度为 n ，初始值全为 false ，表示每个节点初始时都没有父节点。 遍历 leftChild 和 rightChild 数组： 对于 leftChild[i] ，如果它的值不为 -1 ，则将 hasParent[leftChild[i]] 标记为 true ，表示这个左子节点有了父节点 i 。 对于 rightChild[i] ，做同样的处理。 遍历结束后，检查 hasParent 数组。理论上，一棵有效的二叉树应该有且仅有一个节点的 hasParent 值为 false ，这个节点就是根节点。如果 hasParent 数组中 false 的个数不为 1，说明要么没有根（每个节点都有父节点，形成了环），要么有多个根（森林），都直接返回 false 。 步骤 2：从根节点开始深度优先搜索 假设我们找到了一个候选根节点 root 。 我们创建一个整数数组 visited ，长度为 n ，用来标记每个节点的状态。我们可以用 0 表示“未访问”， 1 表示“正在访问”（在本次DFS的递归栈中）， 2 表示“已访问”（已从递归栈中弹出，其所有后代都已处理完毕）。 我们从 root 开始，进行DFS。DFS函数 dfs(node) 的逻辑如下： 首先检查当前节点 node 的状态： 如果 visited[node] == 1 ，说明我们在同一条DFS路径上又遇到了这个节点，这表示存在环，立即返回 false 。 如果 visited[node] == 2 ，说明这个节点及其后代已经被完整探索过，为了避免重复工作，直接返回 true 。 将当前节点状态标记为 1 （正在访问）。 递归地探索左子节点和右子节点： 如果 leftChild[node] != -1 ，则递归调用 dfs(leftChild[node]) 。如果递归返回 false ，说明在左子树中发现了问题（环或不连通），本层也直接返回 false 。 对右子节点 rightChild[node] 做同样的处理。 探索完所有子节点后，将当前节点状态标记为 2 （已访问）。 如果整个过程没有提前返回 false ，说明从当前节点 node 开始的子树是有效的，返回 true 。 步骤 3：检查连通性 在调用完从根节点开始的DFS后，我们需要检查是否所有节点都被访问过。 遍历 visited 数组，检查是否所有节点的状态都是 2 （已访问）。如果不是，说明有节点无法从根节点到达，结构不连通，返回 false 。 如果所有节点都是 2 ，则说明这是一棵有效的二叉树，返回 true 。 图解与边界条件 示例1（有效） ： n = 4 leftChild = [ 1, -1, 3, -1 ] rightChild = [ 2, -1, -1, -1 ] 结构：节点0是根，左子为1，右子为2；节点1的左子为3。 步骤1： hasParent 数组为 [ false, true, true, true ]，只有节点0无父节点，是根。 步骤2：从节点0开始DFS，访问顺序0->1->3->2。所有节点状态变为2，无环。 步骤3：所有节点已访问。返回 true 。 示例2（有环，无效） ： n = 4 leftChild = [ 1, -1, 3, -1 ] rightChild = [ 2, 3, -1, -1 ] 结构：节点0（根）的右子2的左子是3，但节点3又同时是节点0的左子1的右子？实际上，这会导致节点3有两个父节点（1和2），这首先违反了“每个节点只有一个父节点”的规则。在我们的算法中， hasParent[3] 会被设为 true 两次，但这不是关键。关键是在DFS中，当从节点0探索左子树（节点1）和右子树（节点2）时，节点3会被访问两次。如果第一次访问（从节点1）将其标记为2，第二次访问（从节点2）发现它是2，会直接返回true，不会报错。但我们需要在步骤1中就通过 hasParent 检查来防止这种情况。更复杂的环，比如节点0的左子指向节点1，节点1的右子指向节点0，我们的DFS在探索节点0时，会进入节点1，又从节点1回到节点0，此时节点0的状态是1（正在访问），从而检测到环并返回false。 边界条件 ： n = 1, leftChild = [ -1], rightChild = [ -1]。单个节点，是有效的二叉树。 hasParent[0]=false ，是根。DFS访问它，然后检查所有节点已访问。返回 true 。 n = 0， 但题目中 n >= 1，所以不用特殊处理。 总结 这道题将二叉树结构的验证转化为了图的遍历问题。通过 统计入度（父节点数） 找到唯一的根节点，然后通过 带有状态标记的深度优先搜索 来检查从该根节点出发，图中是否存在环以及是否所有节点都能被访问到。这是一种非常经典的、结合了拓扑排序思想和图遍历思想的解法。