# 1361. Validate Binary Tree Nodes
###### tags: `LeetCode`
## **Link**
https://leetcode.com/problems/validate-binary-tree-nodes/

## **Code**

class Solution {
public:

    bool dfs(int n, int &cnt, vector<int>& leftChild, vector<int>& rightChild, vector<bool> &visited)
    {
        bool rt=true;
        if(visited[n]) // 一棵樹的每個點只能走一次
            return false;
        visited[n]=true;
        ++cnt; // 算總共走了幾個點，最後特判要用
        if(leftChild[n]!=-1) // 有左節點就往下走
            rt=rt&dfs(leftChild[n],cnt,leftChild,rightChild,visited);
        if(rightChild[n]!=-1) // 有右節點就往下走
            rt=rt&dfs(rightChild[n],cnt,leftChild,rightChild,visited);
        return rt;
    }

    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) 
    {
        vector<bool> haveParent(n,false),visited(n,false);
        int check=0;
        for(int i=0;i<n;++i) // 把所有節點的parent記下來
        {
            if(leftChild[i]!=-1)
            {
                if(!haveParent[leftChild[i]]) // 這個節點沒有parent的話
                {
                    ++check;
                    haveParent[leftChild[i]]=true;
                }
                else // 這個節點已經有parent的話=>一棵樹的任一個節點都不會有兩個parent=>這棵樹不合法
                    return false;
            }
            if(rightChild[i]!=-1)
            {
                if(!haveParent[rightChild[i]]) // 這個節點沒有parent的話
                {
                    ++check;
                    haveParent[rightChild[i]]=true;
                }
                else // 這個節點已經有parent的話=>一棵樹的任一個節點都不會有兩個parent=>這棵樹不合法
                    return false;
            }
        }
        if(check!=n-1) // 如果邊的數量不是n-1=>這不是一棵樹（一棵樹的邊必為n-1條）
            return false;
        bool ans;
        int cnt=0; // 用來算走過的總結點=>就算是n-1條邊，也不一定是一棵樹（可能出現雙向邊或是環）
        for(int i=0;i<n;++i) // 找根節點
            if(!haveParent[i]) // 沒有parent的就是根節點（唯一）
                ans=dfs(i,cnt,leftChild,rightChild,visited);
        if(cnt!=n) // 如果dfs走過的點不是n個，表示可能有出現雙向邊或是環=>不是合法的樹
            return false;
        return ans; // 回傳dfs結果
    }
};

## date
**2023.01.17**

{%hackmd @nnks8908/background_leetcode %}