二叉树前序遍历（递归以及非递归）-蒲公英云

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

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

二叉树前序遍历

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

请看大屏幕。。。。

在这里插入图片描述

上图是一棵二叉树，前序遍历结果：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:
  vectorv;
  vector 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 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;