Validate Binary Tree Nodes ใน C++ : ตรวจสอบ Binary Tree Valid จาก Left/Right Child Arrays

ให้ n Nodes (0..n-1) และ Array leftChild, rightChild โดย leftChild[i] = Left Child ของ Node i (-1 ถ้าไม่มี) ตรวจสอบว่า **Nodes ทั้ง n ตัวนี้สร้าง Binary Tree ได้เพียงต้นเดียวและ Valid** หรือไม่

Valid Binary Tree Conditions:

1. มี **Root เพียง 1 ตัว** (ไม่มี Parent)
2. **ไม่มี Cycle** (DFS Visit Node ซ้ำ -> Invalid)
3. **ทุก Node ถูก Visit** (Connected, ไม่มี Disconnected Component)
4. แต่ละ Node มี Parent **สูงสุด 1 คน** (Enforced by Array Structure แต่ต้องเช็ค Cycle)

ตัวอย่าง

n=4
leftChild  = [1, -1, 3, -1]
rightChild = [2, -1, -1, -1]

Tree:
    0
   / \
  1   2
 /
3
Valid: true

แนวทาง: DFS + Visited Set + Root Finding

1. หา **Root**: Node ที่ **ไม่เคยเป็น Child** ของใคร (ไม่ปรากฏใน leftChild/rightChild)
2. DFS จาก Root:
   • ถ้าเจอ Node ที่ Visited แล้ว -> **Cycle** -> False
   • Mark Visited, Recurse Left/Right
3. หลัง DFS: เช็คว่า **Visited Count == n** (All nodes connected)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool dfs(int node, vector<int>& leftChild, vector<int>& rightChild, vector<bool>& visited) {
        if (visited[node]) return false; // Cycle detected
        visited[node] = true;

        bool valid = true;
        if (leftChild[node] != -1)
            valid &= dfs(leftChild[node], leftChild, rightChild, visited);
        if (rightChild[node] != -1)
            valid &= dfs(rightChild[node], leftChild, rightChild, visited);
        return valid;
    }

    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        // 1. Find Root (Node with no parent)
        vector<bool> hasParent(n, false);
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) hasParent[leftChild[i]] = true;
            if (rightChild[i] != -1) hasParent[rightChild[i]] = true;
        }
        int root = -1;
        for (int i = 0; i < n; i++) if (!hasParent[i]) { root = i; break; }
        if (root == -1) return false; // No root (Cycle or Multiple roots)

        // 2. DFS from Root + Cycle Check
        vector<bool> visited(n, false);
        bool valid = dfs(root, leftChild, rightChild, visited);

        // 3. Check All Nodes Visited (Connected)
        for (int i = 0; i < n; i++) if (!visited[i]) return false;

        return valid;
    }
};

Input / Output

Input:  4 [1,-1,3,-1] [2,-1,-1,-1]
Output: 1 (true)

ความซับซ้อน (Complexity)

• Time: O(N)
• Space: O(N) — Visited Array + Recursion Stack

จุดสำคัญ

• หา Root โดยเช็ค "ไม่มี Parent" (O(N))
• DFS เช็ค Cycle (Visited Array) และ Connectedness (Count Visited)
• Array Structure ให้ Parent ≤ 1 แล้ว ไม่ต้องเช็ค Multiple Parents แยก

LeetCode 1361 ครับ