【题目】
Given a binary tree, return thepreordertraversal of its nodes' values.
For example:
Given binary tree{1,#,2,3}
,
1
\
2
/
3
return[1,2,3]
.
Note:Recursive solution is trivial, could you do it iteratively?
【代码一】
/*********************************
* 日期:2014-10-15
* 作者:SJF0115
* 题号: 144.Binary Tree Preorder Traversal
* 来源:https://oj.leetcode.com/problems/binary-tree-preorder-traversal/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <malloc.h>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> v;
void PreOrder(TreeNode *root){
if (root == NULL){
return;
}
v.push_back(root->val);
PreOrder(root->left);
PreOrder(root->right);
}
vector<int> preorderTraversal(TreeNode *root) {
PreOrder(root);
return v;
}
};
//按先序序列创建二叉树
int CreateBTree(TreeNode* &T){
char data;
//按先序次序输入二叉树中结点的值(一个字符),‘#’表示空树
cin>>data;
if(data == '#'){
T = NULL;
}
else{
T = (TreeNode*)malloc(sizeof(TreeNode));
//生成根结点
T->val = data-'0';
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
vector<int> v = solution.preorderTraversal(root);
for(int i = 0;i < v.size();i++){
cout<<v[i]<<endl;
}
}
【代码二】
非递归实现
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> v;
stack<TreeNode*> s;
TreeNode* p = root;
//栈不空或者p不空时循环
while(p != NULL || !s.empty()){
if(p != NULL){
//访问根节点
v.push_back(p->val);
//根节点插入栈中,用来访问右子树
s.push(p);
//遍历左子树
p = p->left;
}
else{
//左子树访问完毕,访问右子树
p = s.top();
s.pop();
p = p->right;
}
}
return v;
}
};
【代码三】
/*------------------------------------------------
* 日期:2015-03-25
* 作者:SJF0115
* 题目: 144.Binary Tree Preorder Traversal
* 来源:https://oj.leetcode.com/problems/binary-tree-preorder-traversal/
* 结果:AC
* 来源:LeetCode
* 博客:
------------------------------------------------------*/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// 二叉树节点结构
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
if(root == nullptr){
return result;
}//if
stack<TreeNode*> s;
s.push(root);
TreeNode *node;
while(!s.empty()){
node = s.top();
s.pop();
result.push_back(node->val);
// 右子树
if(node->right){
s.push(node->right);
}//if
// 左子树
if(node->left){
s.push(node->left);
}//if
}//while
return result;
}
};
// 1.创建二叉树
void CreateTree(TreeNode* &root){
int val;
//按先序次序输入二叉树中结点的值,‘-1’表示空树
cin>>val;
// 空节点
if(val == -1){
root = nullptr;
return;
}//if
root = new TreeNode(val);
//构造左子树
CreateTree(root->left);
//构造右子树
CreateTree(root->right);
}
int main() {
freopen("C:\\Users\\Administrator\\Desktop\\c++.txt", "r", stdin);
TreeNode* root = nullptr;
vector<int> result;
// 创建二叉树
CreateTree(root);
Solution solution;
result = solution.preorderTraversal(root);
for(int i = 0;i < result.size();++i){
cout<<result[i]<<" ";
}
cout<<endl;
return 0;
}
分享到:
相关推荐
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
leetcode 530 力扣在线评委 # 问题 困难 解决方案 1 简单的 2 中等的 3 中等的 12 中等的 22 中等的 39 中等的 94 中等的 108 中等的 122 中等的 136 中等的 144 中等的 167 中等的 238 中等的 260 中等的 268 中等...
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
LeetCode笔记本docsifyjsLeetCode算法Java c / c ++ javascript的基本知识简单的1. Two Sum 704. Classical Binary Search2.... Binary Tree Inorder Traversal144. Binary Tree Preorder Traversal145. Binary Tree
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
102 Binary Tree Level Order Traversal.js(二叉树级订单Traversal.js) 103 Binary Tree Zigzag Level Order Traversal.js(二叉树之字形级别顺序Traversal.js) 104 Binary Tree.js的最大深度 105从Preorder和...
105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-...
Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique Binary Search Trees Unique Binary Search Trees II Validate Binary...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。因为LeetCode题目接口更为规范,而且测试数据也更为全面。 牛客网 LeetCode 二维数组中的查找 240. ...
[105_construct-binary-tree-from-preorder-and-inorder-traversal.cpp] [106_construct-binary-tree-from-inorder-and-postorder-traversal.cpp] [107_binary-tree-level-order-traversal-ii.cpp] [108_convert-...
leetcode 530 LeetCode 问题列表,包括锁定的问题。 [1028] Recover a Tree From Preorder Traversal Hard (73.62 %) [1027] Longest Arithmetic Sequence Medium (41.26 %) [1026] Maximum Difference Between Node...
BST_from_preorder_traversal.cpp - 2sum.cpp - remove_adjacent_duplicates.cpp - 子集.cpp - 子集_2.cpp - Remove_Nth_Node_From_End_of_List.cpp - invert_Binary_Tree.cpp - 对称树.cpp - BST_Or_Not.cpp - ...
lru cache leetcode leetcode 记录自己刷leetcode时遇到的一些值得记下来的...binary-tree-preorder-traversal n-queens-ii populating-next-right-pointers-in-each-node sum-root-to-leaf-numbers best-time-to-buy
binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning...
construct-binary-tree-from-preorder-and-inorder-traversal 无官方题解 106 construct-binary-tree-from-inorder-and-postorder-traversal 无官方题解 116 populating-next-right-pointers-in-eac
java lru leetcode ...Tree/BinaryTree BST HashTable Disjoint Set Trie BloomFilter LRU Cache Algorithm General Coding InOrder/PreOrder/PostOrder Traversal Greedy Recursion/Backtrace Breadth-fi
poj与leetcode 自述文件 介绍 本repo由鞠承佑、钟恺健、王少泽创建。 它在帐户SuanFaRuoji(算法弱鸡)下...└──889_construct_binary_tree_from_preorder_and_postorder_traversal └──zkj_python.py 我们的任务