原题:
Given a binary tree, return the preorder traversal of its nodes' values.
=>给出一个二叉树,返回先序遍历的所有的节点值
For example:
例如:
Given binary tree {1,#,2,3}
,
给出下面的二叉树
1
\
2
/
3
return [1,2,3]
.
返回[1,2,3]
Note: Recursive solution is trivial, could you do it iteratively?
=》注意:递归的算法是很普通,能不能不要递归呢?
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
}
};
晓东解析:
这个题目用递归来实现的确很简单,就是先遍历左,再遍历右。那非递归的算法就是先一直左到底,并把这些所有的左都压到一个栈里面,然后到最后,再一个个pop出来,每pop一个,对它的右子树再进行一次类似的遍历就可以了。
代码实现:
1、递归实现
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vector<int> result;
vector<int> left;
vector<int> right;
if(root == NULL) return result;
result.push_back(root->val);
left = preorderTraversal(root->left);
right = preorderTraversal(root->right);
if(left.size() != 0)
result.insert(result.end(), left.begin(), left.end());
if(right.size() != 0)
result.insert(result.end(), right.begin(), right.end());
return result;
}
};
运行结果:
67 / 67test cases passed.
|
Status:
Accepted
|
Runtime: 20 ms
|
2、非递归实现:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
stack<TreeNode*> TreeStack;
vector<int> result;
if(root == NULL) return result;
while(root || !TreeStack.empty()){
while(root){
TreeStack.push(root);
result.push_back(root->val);
root = root->left;
}
root = TreeStack.top();
TreeStack.pop();
root = root->right;
}
}
};
运行结果:
67 / 67test cases passed.
|
Status:
Accepted
|
Runtime: 12 ms
|
希望大家有更好的算法能够提出来,不甚感谢。
若您觉得该文章对您有帮助,请在下面用鼠标轻轻按一下“顶”,哈哈~~·
分享到:
相关推荐
Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-...
二叉树遍历可视化器 该项目是一个二叉树遍历可视化工具。 观看。 支持的遍历: 1. Level Order Traversal 2. Depth First Traversal(Pre-order,Post-order,In-order) 您可以在此处了解有关这些算法的更多信息: ...
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
105.construct_binary_tree_from_preorder_and_inorder_traversal从前序
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和...
数据结构二叉树功能展示包括以完全前序序列创建二叉树"; cout<<" create in preorder and in... cout<<" if complete binary tree ... 判断是否是一颗二叉树"; cout打印该树"; cout回收该树"; cout退出操作";
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...
重建二叉树 105. Construct Binary Tree from Preorder and Inorder Traversal 用两个栈实现队列 232. Implement Queue using Stacks 旋转数组的最小数字 153. Find Minimum in Rotated Sorted Array 斐波那契数列 ...
Data Structure and Algorithms,数据结构和算法,纯英文版,介绍了链表,二叉树等数据结构 Contents 1 Introduction 1 1.1 What this book is, and what it isn't . . . . . . . . . . . . . . . . 1 1.2 Assumed ...