服务器之家

服务器之家 > 正文

二叉树的递归和非递归的遍历算法模板

时间:2021-09-15 23:29     来源/作者:Python之王

二叉树的递归和非递归的遍历算法模板

刷Leetcode,需要知道一定的算法模板,本次先总结下二叉树的递归和非递归的遍历算法模板。

二叉树的四种遍历方式,前中后加上层序遍历。对于二叉树的前中后层序遍历,每种遍历都可以递归和循环两种实现方法,且每种遍历的递归实现都比循环实现要简洁。下面做一个小结,看了《代码随想录》哈工大大佬的刷题指南,深受启发,因,下面代码有一定来源《代码随想录》。

递归

下面伪代码是二叉树遍历的递归算法模板,顺序是中左右,也就是前序遍历,改变中左右三行代码的顺序,前中后序三种递归遍历轻松解决。

  1. defpreorderTraversal(root:TreeNode)->List[int]:
  2. res=[]
  3. defhelp(root):
  4. ifnotroot:return
  5. res.append(root.val)#中
  6. help(root.left)#左
  7. help(root.right)#右
  8. help(root)
  9. returnres

对此也提供C++代码,递归算法模板一定要加上终止条件,不然一入递归深似海,从此offer是路人,来源代码随想录。

  1. voidhelp(TreeNode*root,vector<int>@amp;res){
  2. if(root==nullptr){
  3. return;
  4. }
  5. res.push_back(root->val);//中
  6. help(root->left,res);//左
  7. help(root->right,res);//右
  8. }
  9.  
  10.  
  11. vector<int>preorderTraversal(TreeNode*root){
  12. vector<int>res;
  13. help(root,res);
  14. returnres;
  15. }

迭代

迭代遍历二叉树的比递归难度加大,其实使用了一个栈的数据结构,《代码随想录》非常巧妙的使用空指针来作标记,原理是将处理的节点放入栈之后,紧接着放入一个空指针作为标记。

由于栈是先进后出,所以前序遍历的顺序中左右,在加到栈中,需要反过来进行添加,每添加一个元素在后面添加一个空指针,在Python中也可以使用None来代替。

下面是具体的伪代码,至于中序和后序遍历,改下向栈中添加节点的顺序即可。

  1. defpreorderTraversal(root:TreeNode)->List[int]:
  2. result=[]
  3. st=[]
  4. #1、判断root
  5. ifroot:
  6. st.append(root)
  7. whilest:
  8. node=st.pop()
  9. ifnode!=None:
  10. #右左中添加到栈中,然后中左右拿出
  11. ifnode.right:#右
  12. st.append(node.right)
  13. ifnode.left:#左
  14. st.append(node.left)
  15. st.append(node)#中
  16. #添加一个空指针记录节点
  17. st.append(None)
  18. else:
  19. #node是空指针,那么下一个就是加入的节点
  20. node=st.pop()
  21. result.append(node.val)
  22. returnresult

下面是具体的C++代码,由于C++中的stack中pop之后,没有返回值,因此需要额外注意。

  1. vector<int>preorderTraversal(TreeNode*root){
  2. vector<int>res;
  3. stackst;
  4. if(root!=nullptr)st.push(root);
  5. while(!st.empty()){
  6. TreeNode*node=st.top();
  7. if(node!=nullptr){
  8. st.pop();
  9. if(node->right)st.push(node->right);
  10. if(node->left)st.push(node->left);
  11. st.push(node);
  12. st.push(NULL);
  13. }else{
  14. //需要额外注意下
  15. st.pop();
  16. node=st.top();
  17. st.pop();
  18. res.push_back(node->val);
  19. }
  20. }
  21. returnres;
  22.  
  23. }

层次遍历

其实,树的遍历也分为两种,分别是深度优先遍历和广度优先遍历。关于树的不同深度优先遍历(前序,中序和后序遍历)就是递归和非递归的写法。广度优先遍历在树中,就是层次遍历。

在二叉树的层级遍历中,我们需要用到队列这个数据结构,帮助我们完成遍历。

在Python伪代码中,

  1. deflevelOrder(root:TreeNode)->List[List[int]]:
  2. #1、判断root
  3. ifnotroot:
  4. return[]
  5. #把root添加到quene中
  6. quene=[root]
  7. out_list=[]
  8. whilequene:
  9. #while第一步就是求length
  10. length=len(queue)
  11. in_list=[]
  12. for_inrange(length):
  13. #在C++中,这里需要两行
  14. curnode=queue.pop(0)#(默认移除列表最后一个元素)这里需要移除队列最头上的那个
  15. in_list.append(curnode.val)
  16. ifcurnode.left:queue.append(curnode.left)
  17. ifcurnode.right:queue.append(curnode.right)
  18. out_list.append(in_list)
  19. returnout_list

通过上面的Python伪代码,进行书写更高效的C++代码。

  1. classSolution{
  2. public:
  3. vectorint>>levelOrder(TreeNode*root){
  4. vectorint>>res;
  5. queueque;
  6. //判断root
  7. if(root!=nullptr)que.push(root);
  8. while(!que.empty()){
  9. //开始先求队列的长度
  10. intsize=que.size();
  11. vector<int>vec;
  12. //迭代添加节点元素
  13. for(inti=0;i<size;i++){
  14. TreeNode*node=que.front();
  15. que.pop();
  16. vec.push_back(node->val);
  17. if(node->left)que.push(node->left);
  18. if(node->right)que.push(node->right);
  19. }
  20. res.push_back(vec);
  21. }
  22. returnres;
  23. }
  24. };

上述为树的遍历模板。其实本质上也是深度优先遍历与广度优先遍历的算法模板,许多其它操作都是建立在树遍历操作的基础之上,因此掌握树的所有遍历方法,等于解决了一半树的题目。

原文链接:https://mp.weixin.qq.com/s/dqpQSMx9_iZ4s7z_6L-sNg

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
返回顶部