vlambda博客
学习文章列表

力扣--二叉树的深度遍历

​有人相爱,有人开车去看海,有人连力扣第一题都做不出来。哈哈哈,这是之前看到的听说在力扣第一题下面的评论,今天我们不做第一题,来看看那棵又大又高的树,计算机中的树跟我们生活中不一样,是倒着放的,根在上,叶子在最下面。那在计算机中有什么用呢?那就多了去了,数据的存储结构,文件目录的结构,常见的排序,我们在数据库中查找都是底层应用了树的结构,可以说非常重要了。而在笔试和面试中也是考察重点,我们今天先来看看树的遍历方式的前三种,先序,中序和后序遍历。

一般树都由根节点和子节点组成,先序遍历就是先访问根节点,再访问左子树,最后访问右子树;中序遍历就是,先访问左子树,再根节点,再右子树;后序就是先左子树,再右子树,最后根节点。所以可以看出我们说的前中后表示根节点的顺序,根节点第一个访问就是前序,以此类推。

1、二叉树的遍历

解题思路:三部曲

1、确定递归函数的参数和返回值类型

2、确定终止条件

3、确定单层递归的逻辑:每一层递归该如何实现,即递归的是实现是在这一步进行的

二叉树的节点定义:
struct TreeNode
{
int val;  //存储节点的值
TreeNode * left;  //存储结点的左指针
TreeNode * right;  //存储结点的右指针
TreeNode(int x):val(x),left(NULL),right(NULL){}  //构造函数,初始化一个节点时,左右指针都为空
};
1.1 二叉树的前序遍历


方法一:递归的方法

class solution
{
public:
   //解题思路:按照递归的三部曲来
   //1、确定递归函数及参数,我们需要递归遍历节点就需要传入结点的信息,同时还需要一个数组来保存我们遍历的元素值
   void traversal(TreeNode * cur,vector<int>&result)  // 因为不需要返回值,所以返回类型为void
  {
       if(cur==NULL)  //2、终止条件如果结点为空,说明树为空,直接返回,不需要遍历
      {
           return;
      }
       //不为空的话就执行下面的操作
       result.push_back(cur->val);  //将当前节点的元素值保存下来
       traversal(cur->left,result);  //3、遍历当前节点的左子树,这里就是陷入递归的步骤,函数自己调用自己
       traversal(cur->right,result);  //3、遍历当前结点的右子树,同上
  }
   vector<int>preorderTraversal(TreeNode * root)
  {
       vector<int>result;  //创建一个数组来保存元素
       traversal(root,result);  //函数调用
       return result;
  }
   
}

方法二:迭代法

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
   vector<int>preorderTraversal(TreeNode* root) {
       vector<int>result;  //创建数组存储遍历的值
       stack<TreeNode*>st;  //创建一个栈用来存储遍历的每一个树结点
       if(root == nullptr)
      {
           return result;  //当根节点为空时,直接返回,不再遍历
      }
       st.push(root);  //将根节点压入栈中
       while(!st.empty())
      {
           TreeNode * node = st.top();  //新建一个结点指向栈顶元素
           st.pop();  //弹出栈顶元素
           result.push_back(node->val);  //将弹出去的栈顶元素的值保存到我们的结果文件里面
           if(node->right)
          {
               st.push(node->right);  //然后把刚才的节点的右子树结点放入栈,因为栈是先进后出
               //所以,右节点先进去,再放入左节点,就可以得到中左右的顺序
          }
           if(node->left)
          {
               st.push(node->left);
          }

      }
       
       return result;

  }
};

总结:递归方法相对简单,迭代法需要利用一个栈来存储结点,一般笔试或者面试的时候都考察迭代法。

1.2 二叉树的中序遍历

方法一:递归

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:

/*
方法一:递归,采用三部曲
*/

   void traversal(TreeNode * cur,vector<int>&result)
  {
       if(cur==nullptr)  //当前结点为空直接返回
      {
           return;
      }

       //不为空的话执行下面的操作
       traversal(cur->left,result); //先访问左子树
       result.push_back(cur->val);  //再访问根节点
       traversal(cur->right,result);  //最后访问右子树

  }
   vector<int> inorderTraversal(TreeNode* root) {
       vector<int>result;
       traversal(root,result);  //函数调用
       return result;

  }
};

方法二:迭代法

 //方法二:迭代法
   vector<int> inorderTraversal(TreeNode* root) {
       stack<TreeNode*>st;  //创建一个栈来存储结点
       vector<int>result;  //定义vector来存储最终的结果
       TreeNode * cur = root;  //定义一个结点指针指向根节点

       /*
       下面就是主要的思路:因为是中序遍历,所以先要遍历左子树,再遍历根节点,再遍历右子树,
       所以需要一直找到最左边的那个结点,先遍历它,再一个一个结点递归,最后到右子树,就可以了
       */

       while(cur!=NULL ||!st.empty())  //当结点不为空就一直遍历
      {
           if(cur != NULL)  //如果当前节点不为空,就加入到栈中
          {
               st.push(cur);
               cur=cur->left;  //一直找左子树,即最底层,直到结点为空
          }
           else  //即已经到了最下层的节点了,这时候需要对存储在栈中的元素进行处理
          {
               cur=st.top();  //指向栈顶元素
               st.pop();  //出栈
               result.push_back(cur->val);  
               cur=cur->right;  //遍历右子树
          }
      }
       return result;

  }

总结:对于中序遍历就是先根据当前结点是否为空找到最左端的子树,再根据栈是否为空对每一个结点进行处理,当两者都能不满足条件的时候,就可以得到处理结果

1.3 二叉树的后序遍历

方法一:递归

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:

/*
方法一:递归法,同样是三部曲
*/
   void traversal(TreeNode * cur,vector<int>&vec)
  {
       if(cur==NULL)
      {
           return;
      }

       //不为空的话执行下面代码
       traversal(cur->left,vec);  //递归左子树
       traversal(cur->right,vec);  //递归右子树
       vec.push_back(cur->val);  //遍历根节点
  }
   vector<int> postorderTraversal(TreeNode* root) {
       vector<int>result;
       traversal(root,result);
       return result;
  }
};

方法二:迭代法

分析:对于前序遍历,我们的遍历顺序是中左右,我们调换左右子树的遍历顺序就可以得到中右左,再对结果反转,就可以得到左右中,就得到后序遍历的算法

方法二:迭代法
*/
   vector<int> postorderTraversal(TreeNode* root) {
       stack<TreeNode *>st;
       vector<int>result;
       if(root==NULL)
      {
           return result;
      }
       st.push(root);
       while(!st.empty())
      {
           TreeNode * cur = st.top();
           st.pop();  //将栈顶元素弹出
           result.push_back(cur->val);  //处理根节点
           if(cur->left)
          {
               st.push(cur->left);  //先将左节点放进去,后出来
          }
           if(cur->right)
          {
               st.push(cur->right);  //后将右节点放进去,先出来
          }
           //此时的顺序是中右左
      }
       reverse(result.begin(),result.end());  //反转就可以得到中左右
       return result;
  }

总结:二叉树的前、中、后序三种遍历方式对于递归来说,采用的思路都是一致的,但是采用迭代法的话,就会存在差距,迭代法对于前序和后序遍历比较相似,相互反转即可,都是用栈来遍历;而对于中序比较麻烦,需要根据指针来遍历。