[leetcode 브러시] 창고의 방식은 먼저 두 갈래 나무를 서열한다.
5.1.1 Binary Tree Preorder Traversal
묘사
Given a binary tree, return the preorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3},
Note: Recursive solution is trivial, could you do it iteratively?
분석: 창고나 모리스로 두루 돌아다닌다.
실현: makeTree () 방법을 추가하여 필요한 두 갈래 나무를 생성합니다.
#include<vector>
#include<iostream>
#include<stdlib.h>
#include<stack>
#include<vector>
#include<cmath>
// #include<iterator>
using namespace std;
static int count = 0;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
//
vector<int> preorderTraversal(TreeNode* root){
vector<int> result;
stack<TreeNode *> stackTree;
TreeNode* p = root;
if(p != nullptr){
stackTree.push(root);
}
while(!stackTree.empty()){
p = stackTree.top();
stackTree.pop();
result.push_back(p->val);
if(p->right != nullptr) stackTree.push(p->right);
if(p->left != nullptr) stackTree.push(p->left);
}
return result;
}
int treeDeep(int n){
int i = 0;
if( n == 1){
return 2;
}else{
while(i < 20){
if(n > pow(2,i)-2 && n <= pow(2,i+1)-2){
return (i+1);
}
i++;
}
}
return 0;
}
void printTree(TreeNode *root){
cout<<root->val<<" ";
if(root->left != nullptr){
printTree(root->left);
}
if(root->right != nullptr){
printTree(root->right);
}
}
TreeNode* selectTree(TreeNode *root,int k){
cout<<root->val<<",";
if(root->left != nullptr){
count++;
cout<<"left:"<<count<<";"<<endl;
cout<<root->left->val<<",";
if(count == k){
return root->left;
}
}
if(root->right != nullptr){
count++;
cout<<"right:"<<count<<";"<<endl;
cout<<root->right->val<<",";
if(count == k){
return root->right;
}
}
selectTree(root->left,k - count);
selectTree(root->right,k - count);
}
void makeTree(TreeNode* root,int k){
TreeNode *tmpTree = new TreeNode(1);
sranddev();
tmpTree->val = rand()%100;
if(count < k && root->left == nullptr){
root->left = tmpTree;
count++;
}else if(count < k && root->right == nullptr){
root->right = tmpTree;
count++;
}
if(count < k){
makeTree(root->left,k);
makeTree(root->right,k);
}
}
int main(){
TreeNode *root = new TreeNode(10);
int size;
size = 10;
TreeNode *root1,*root2;
root1 = root2;
// for(int i = 1; i < 10;++i){
// int deep = treeDeep(i);
// cout<<"i="<<i<<"deep="<<deep<<endl;
// TreeNode *tmpTree = new TreeNode(1);
// sranddev();
// tmpTree->val = rand()%100;
// if(i % 2 == 1){
// root1 = root;
// for(int j = 0; j < deep-1 &&(!root1);j++){
// root1 = root1->left;
// }
// root1->left = tmpTree;
// }else{
// root2 = root;
// for(int j = 0; j < deep-1 && (!root2);j++){
// root2 = root2->right;
// }
// root2->right = tmpTree;
// }
// }
makeTree(root,10);
printTree(root);
cout<<endl;
// selectTree(root,2);
// cout<<endl;
vector<int> res;
res = preorderTraversal(root);
for(vector<int>::iterator it = res.begin(); it != res.end();it++){
cout<<*it<<" ";
}
cout<<endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.