LeetCode Weekly Contest 177 2問目 - Validate Binary Tree Nodes [1361]

Source

LeetCode Weekly Contest 177
問題文

問題概要

省略

解法

省略

cLay（version 20200227-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

int N, vis[1d4], deg[1d4];
vector<int> lf, rg;

void solve(int n){
  vis[n]++;
  if(vis[n]!=1) return;

  if(lf[n]>=0) solve(lf[n]);
  if(rg[n]>=0) solve(rg[n]);
}

class Solution {
public:
  bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
    N = n;
    lf = leftChild;
    rg = rightChild;
    rep(i,N) vis[i] = deg[i] = 0;

    rep(i,N){
      if(lf[i] >= 0) deg[lf[i]]++;
      if(rg[i] >= 0) deg[rg[i]]++;
    }

    rep(i,N) if(deg[i] == 0) break;
    if(i==N) return false;

    solve(i);
    rep(i,N) if(vis[i]!=1) return false;

    return true;
  }
};

Current time: 2024年04月19日12時31分31秒
Last modified: 2020年02月29日15時28分28秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)