原题:
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单题讲解系列】
先序遍历(Preorder Traversal)是遍历二叉树的一种方法,它按照“根-左-右”的顺序访问树中的每个节点。在本主题中,我们将探讨如何实现先序遍历以及将其结果以树状打印出来。 先序遍历是一种递归算法,其基本步骤...
1. **先序遍历**(Preorder Traversal) 先序遍历遵循以下规则: - 首先访问根节点。 - 然后递归地遍历左子树。 - 最后遍历右子树。 使用递归算法实现先序遍历,基本步骤如下: - 如果树为空,则返回。 - ...
- **先序遍历(Preorder Traversal)**:访问顺序为“根节点 -> 左子树 -> 右子树”。 - **中序遍历(Inorder Traversal)**:访问顺序为“左子树 -> 根节点 -> 右子树”。 - **后序遍历(Postorder Traversal)**:访问...
本文将详细解析二叉树的三种基本遍历方式:先序遍历、中序遍历和后序遍历。 #### 1. 先序遍历(Pre-order Traversal) 先序遍历遵循“根节点→左子树→右子树”的顺序访问二叉树的节点。具体步骤如下: 1. 访问根...
在这个名为"Binary tree traversal.zip"的压缩包中,包含了作者在算法课上完成的一个关于二叉树遍历的作业。这个作业使用C++编程语言,并在Visual Studio 2019环境下编写。以下是关于二叉树遍历的详细知识: 1. **...
105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-...
1. **先序遍历(Preorder Traversal)**: 先序遍历的顺序是:根节点 -> 左子树 -> 右子树。递归算法实现如下: - 如果当前节点为空,返回。 - 访问当前节点。 - 递归地先序遍历左子树。 - 递归地先序遍历右子...
`BinaryTree`类包含了与二叉树相关的操作,如获取树的高度`getTreeHeight()`和各种遍历方法。 二叉树的遍历在算法和数据结构中非常常见,用于查找、插入和删除操作,特别是在二叉搜索树(BST)中。理解这三种遍历...
1. 先序遍历(Preorder Traversal): - 访问根节点 - 遍历左子树(先序) - 遍历右子树(先序) 先序遍历的顺序为“根-左-右”,常用于复制整棵树或者创建树的镜像。 2. 中序遍历(Inorder Traversal): - ...
- 前序遍历 (Preorder Traversal) - 中序遍历 (Inorder Traversal) - 后序遍历 (Postorder Traversal) - 层次遍历 (Level Order Traversal) ##### 2.2 进阶操作 - **查找**: 在二叉树中查找特定的节点。 - **...
二叉树遍历可视化器 该项目是一个二叉树遍历可视化工具。 观看。 支持的遍历: 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 ...
对于二叉搜索树(Binary Search Tree),中序遍历会得到一个按升序排列的序列,因此它常用于排序和查找操作。动画演示中,左子树将先被遍历,然后是根节点,最后是右子树。 3. 后序遍历(Postorder Traversal): ...
二叉树的遍历主要有三种基本方法:前序遍历(Preorder Traversal)、中序遍历(Inorder Traversal)和后序遍历(Postorder Traversal)。 1. **前序遍历**:先访问根节点,然后遍历左子树,最后遍历右子树。用递归...
这个名为“Trees-Binary-Search-Trees-Challenge-1-Source-code”的项目专注于BST的前序遍历(PreOrder Traversal)及其搜索操作的源代码实现。在本文中,我们将深入探讨BST的基本概念、前序遍历的原理以及搜索操作...
1. **先序遍历(Preorder Traversal)** 先序遍历的顺序是:根节点 -> 左子树 -> 右子树。换句话说,先访问根节点,然后递归地访问左子树,最后访问右子树。这种遍历方式常用于复制整个二叉树或者创建其前序表示。 ...
**先序遍历(Preorder Traversal)** 先序遍历遵循以下顺序:首先访问根节点,然后递归地遍历左子树,最后遍历右子树。在代码实现中,通常采用递归或栈来完成这一过程。这种遍历方式常用于复制二叉树或构建与原始树...
二叉树的排序主要指二叉搜索树(Binary Search Tree, BST)。在BST中,每个节点的左子树包含的节点值都小于该节点,而右子树包含的节点值都大于该节点。这种特性使得二叉搜索树在查找、插入和删除操作上具有高效性。...