資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中驗證二叉樹節點
假設我們有 n 個二叉樹節點，編號從 0 到 n - 1，其中節點 I 有兩個子節點 leftChild[i] 和 rightChild[i]，我們必須在僅當所有給定節點恰好形成一個有效的二叉樹時才說真。當節點 i 沒有左子節點時，leftChild[i] 將等於 -1，右子節點也類似。我們必須記住，節點沒有值，並且我們只在此問題中使用節點編號。因此，如果輸入類似於 -
那麼輸出將為真。
為了解決這個問題，我們將遵循以下步驟 -
定義一個名為 dfs 的方法，它將接收 leftChild、rightChild 和 visited
如果節點 n 已被訪問，則返回 false
將節點 n 插入到 visited 集合中
設定 ret := true
如果 n 的 leftChild 不為 -1，則 ret := ret AND dfs(leftChild[node], leftChild, rightChild, visited)
如果 n 的 rightChild 不為 -1，則 ret := ret AND dfs(rightChild[node], leftChild, rightChild, visited)
返回 ret
主方法將如下所示 -
ret := dfs(0, leftChild, rightChild, visited)
設定 allVisited := false
對於 I 範圍從 0 到 n – 1
如果 i 未被訪問，則返回 false
返回 ret
示例（C++）
讓我們看看以下實現以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool dfs(int node, vector <int>& leftChild, vector <int>& rightChild, set <int>& visited){
if(visited.count(node)) return false;
visited.insert(node);
bool ret = true;
if(leftChild[node] != -1){
ret &= dfs(leftChild[node], leftChild, rightChild, visited);
}
if(rightChild[node] != -1){
ret &= dfs(rightChild[node], leftChild, rightChild, visited);
}
return ret;
}
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
set <int> visited;
bool ret = dfs(0, leftChild, rightChild, visited);
bool allVisited = true;
for(int i = 0; i < n; i++){
if(!visited.count(i))return false;
}
return ret;
}
};
main(){
vector<int> v1 = {1,-1,3,-1}, v2 = {2,-1,-1,-1};
Solution ob;
cout << (ob.validateBinaryTreeNodes(4, v1, v2));
}輸入
4 [1,-1,3,-1] [2,-1,-1,-1]
輸出
1
更新於: 2020-04-29
319 次瀏覽
廣告