二叉树前序遍历（递归以及非递归）

怼烎@ 2022-04-24 07:50 233阅读 0赞

## 二叉树前序遍历 ##

对于一种数据结构而言，我们最常见的就是遍历，那么关于二叉树我们该如何去遍历呢？

请看大屏幕 。。。。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]

上图是一棵二叉树，前序遍历结果：1 2 4 5 3 6  
咦，我想你可能会疑惑什么叫做前序遍历，其实很简单，就是按照 根 -》 左 -》 右 的方式去遍历二叉树。

*  首先让我们来看看如何递归的去前序遍历二叉树  
    **注：在这里我特别强调一点，在我们二叉树中，如果采用递归的方式，大部分都采用的根左右的方式，即采用子问题的方式，即先处理跟节点，再处理左子树，再处理右子树的这样一种思想**
 *  前序递归遍历

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int>v;
        vector<int> preorderTraversal(TreeNode* root) {
            if(root!=NULL){
               v.push_back(root->val);      //将根节点放入容器中
               preorderTraversal(root->left);   //处理左子树
               preorderTraversal(root->right);   //处理右子树
            }
            return v;
        }
    };

你没看错，就这么简单，但是是如何递归的你得想清楚，这里我就不做详解了。那么接下来我们再看看非递归的方式

*  前序非递归遍历

/**
     * Definition for a binary tree node.
     * 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) {
            vector<int>v;
            stack<TreeNode*>s;
            TreeNode* cur=root;
            while(cur!=NULL || !s.empty()){
                while(cur!=NULL){
                    v.push_back(cur->val);
                    s.push(cur);
                    cur=cur->left;
                }
                TreeNode* top=s.top();
                s.pop();
                cur=top->right;
            }
            return  v;
        }
    };

这就是前序遍历的非递归方式，这种方式主要是采用栈来完成的。这个过程实在不好画图，所以只能靠大家自行理解了，类似一种搞传销的模式，不断的拉下线。。。。可能比喻不太恰当，不过我感觉还挺像的，哈哈！

**All OVER**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTAzMzE1_size_16_color_FFFFFF_t_70]: /images/20220217/24c6934bcbe14d628f0be343154da013.png