資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究C++ 中的二叉樹的右側檢視
我們假設有一棵二叉樹，如果我們從右側觀察二叉樹，我們只能看到其中的某些元素。我們需要顯示這些元素。如果樹的情況如下所示：
為了解決這個問題，我們將按照如下步驟進行操作：
- 我們將會建立一個輔助方法供深度優先搜尋使用。它將使用 tree_node，一個數組來儲存答案，和層。初始層為 0。深度優先搜尋將按照如下規則進行：
- 如果節點為空，那麼返回
- 如果層 = 答案陣列的長度，那麼將節點的值插入到 ans 陣列中
- dfs(節點的右側，ans，層 + 1)
- dfs(節點的左側，ans，層 + 1)
- 從主函式呼叫 dfs()，使用樹的根節點和一個空陣列，初始層為 0，所以最終形式為：dfs(root，ans)
讓我們檢視以下實現來獲得更清晰的理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
void dfs(TreeNode* node, vector <int>& ans, int level = 0){
if(!node) return;
if(level == ans.size())ans.push_back(node->val);
dfs(node->right, ans, level + 1);
dfs(node->left, ans, level + 1);
}
vector<int> rightSideView(TreeNode* root) {
vector <int> ans;
dfs(root, ans);
return ans;
}
};
main(){
vector<int> v = {1,2,3,NULL,5,NULL,4};
TreeNode *root = make_tree(v);
Solution ob;
print_vector(ob.rightSideView(root));
}輸入
[1,2,3,null,5,null,4]
輸出
[1, 3, 4, ]
更新於： 04-05-2020
150 次瀏覽
廣告