1361. Validate Binary Tree Nodes

Problem Statement

link: LeetCode.cn LeetCode You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

Example:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] Output: false

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1] Output: false

Constraints: n == leftChild.length == rightChild.length 1 <= n <= 104 -1 <= leftChild[i], rightChild[i] <= n - 1

Solution Approach

To validate the binary tree, the algorithm checks that there is exactly one root node, uses DFS to ensure that all nodes are connected without cycles, and confirms that the number of visited nodes matches the total number of nodes.

Algorithm

1. In-Degree Check: Count the in-degree (number of incoming edges) for each node to identify the root node (in-degree of 0). Ensure that there is exactly one root node, as a valid binary tree can only have one root.
2. Cycle and Connectivity Check: Use Depth-First Search (DFS) to traverse the tree starting from the identified root. Check for cycles and confirm that each node is visited only once, ensuring no node has multiple parents.
3. Complete Traversal Verification: After DFS, verify that all nodes have been visited to confirm that the entire graph forms a single connected component, meaning the structure is a valid binary tree.

Implement

    class Solution:
  def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
      in_degree = [0] * n
      for i in range(n):
          if leftChild[i] != -1:
              in_degree[leftChild[i]] += 1
          if rightChild[i] != -1:
              in_degree[rightChild[i]] += 1
      
      root = -1
      for i in range(n):
          if in_degree[i] == 0:
              if root == -1:
                  root = i
              else:
                  return False

      visited = set()
      def dfs(node): 
          if node == -1:
              return True
          if node in visited:
              return False
          visited.add(node) 
          return dfs(leftChild[node]) and dfs(rightChild[node])

      if not dfs(root):
          return False

      return len(visited) == n
      

    
    

Twitter  facebook  Email