`
836811384
  • 浏览: 575342 次
文章分类
社区版块
存档分类
最新评论

Binary Tree Preorder Traversal--二叉树的先序遍历

 
阅读更多

原题:

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

    Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树

    144.Binary Tree Preorder Traversal二叉树的前序遍历【LeetCode单题讲解系列】

    144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】

    Preorder-binary-tree-(tree-print.zip_print binary tree_tree_打印二叉

    先序遍历(Preorder Traversal)是遍历二叉树的一种方法,它按照“根-左-右”的顺序访问树中的每个节点。在本主题中,我们将探讨如何实现先序遍历以及将其结果以树状打印出来。 先序遍历是一种递归算法,其基本步骤...

    学习电脑信息先序遍历后序遍历中序遍历

    1. **先序遍历**(Preorder Traversal) 先序遍历遵循以下规则: - 首先访问根节点。 - 然后递归地遍历左子树。 - 最后遍历右子树。 使用递归算法实现先序遍历,基本步骤如下: - 如果树为空,则返回。 - ...

    Java基础复习笔记08数据结构-二叉树和二叉树的遍历

    - **先序遍历(Preorder Traversal)**:访问顺序为“根节点 -&gt; 左子树 -&gt; 右子树”。 - **中序遍历(Inorder Traversal)**:访问顺序为“左子树 -&gt; 根节点 -&gt; 右子树”。 - **后序遍历(Postorder Traversal)**:访问...

    二叉树遍历输出

    本文将详细解析二叉树的三种基本遍历方式:先序遍历、中序遍历和后序遍历。 #### 1. 先序遍历(Pre-order Traversal) 先序遍历遵循“根节点→左子树→右子树”的顺序访问二叉树的节点。具体步骤如下: 1. 访问根...

    Binary tree traversal.zip

    在这个名为"Binary tree traversal.zip"的压缩包中,包含了作者在算法课上完成的一个关于二叉树遍历的作业。这个作业使用C++编程语言,并在Visual Studio 2019环境下编写。以下是关于二叉树遍历的详细知识: 1. **...

    四平方和定理leetcode-leetcode-practice:个人LeetCode练习代码

    105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-traversal (从中序与后序遍历序列构造二叉树) 112.path-...

    【swjtu】数据结构六_二叉树的遍历算法.zip

    1. **先序遍历(Preorder Traversal)**: 先序遍历的顺序是:根节点 -&gt; 左子树 -&gt; 右子树。递归算法实现如下: - 如果当前节点为空,返回。 - 访问当前节点。 - 递归地先序遍历左子树。 - 递归地先序遍历右子...

    二叉树的遍历 java语言实现

    `BinaryTree`类包含了与二叉树相关的操作,如获取树的高度`getTreeHeight()`和各种遍历方法。 二叉树的遍历在算法和数据结构中非常常见,用于查找、插入和删除操作,特别是在二叉搜索树(BST)中。理解这三种遍历...

    二叉查找树的先序中序后续遍历

    1. 先序遍历(Preorder Traversal): - 访问根节点 - 遍历左子树(先序) - 遍历右子树(先序) 先序遍历的顺序为“根-左-右”,常用于复制整棵树或者创建树的镜像。 2. 中序遍历(Inorder Traversal): - ...

    二叉树详解 binary tree

    - 前序遍历 (Preorder Traversal) - 中序遍历 (Inorder Traversal) - 后序遍历 (Postorder Traversal) - 层次遍历 (Level Order Traversal) ##### 2.2 进阶操作 - **查找**: 在二叉树中查找特定的节点。 - **...

    react-binary-tree:二叉树遍历可视化

    二叉树遍历可视化器 该项目是一个二叉树遍历可视化工具。 观看。 支持的遍历: 1. Level Order Traversal 2. Depth First Traversal(Pre-order,Post-order,In-order) 您可以在此处了解有关这些算法的更多信息: ...

    leetcode-tree

    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遍历-Search source code

    这个名为“Trees-Binary-Search-Trees-Challenge-1-Source-code”的项目专注于BST的前序遍历(PreOrder Traversal)及其搜索操作的源代码实现。在本文中,我们将深入探讨BST的基本概念、前序遍历的原理以及搜索操作...

    数据结构——二叉树的四种遍历

    1. **先序遍历(Preorder Traversal)** 先序遍历的顺序是:根节点 -&gt; 左子树 -&gt; 右子树。换句话说,先访问根节点,然后递归地访问左子树,最后访问右子树。这种遍历方式常用于复制整个二叉树或者创建其前序表示。 ...

    Traverse-binary-tree.rar_traverse

    **先序遍历(Preorder Traversal)** 先序遍历遵循以下顺序:首先访问根节点,然后递归地遍历左子树,最后遍历右子树。在代码实现中,通常采用递归或栈来完成这一过程。这种遍历方式常用于复制二叉树或构建与原始树...

    二叉树的遍历和排序系统

    二叉树的排序主要指二叉搜索树(Binary Search Tree, BST)。在BST中,每个节点的左子树包含的节点值都小于该节点,而右子树包含的节点值都大于该节点。这种特性使得二叉搜索树在查找、插入和删除操作上具有高效性。...

Global site tag (gtag.js) - Google Analytics