二叉树的递归遍历，套路都在这里

二叉树的递归遍历

这次我们要好好谈一谈递归，为什么很多同学看递归算法都是“一看就会，一写就废”。

成都创新互联始终致力于在企业网站建设领域发展。秉承“创新、求实、诚信、拼搏”的企业精神，致力为企业提供全面的网络宣传与技术应用整体策划方案，为企业提供包括“网站建设、成都响应式网站建设、手机网站建设、微信网站建设、微信平台小程序开发、商城网站开发、平台网站建设秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

主要是对递归不成体系，没有方法论，每次写递归算法 ，都是靠玄学来写代码，代码能不能编过都靠运气。

本篇将介绍前后中序的递归写法，一些同学可能会感觉很简单，其实不然，我们要通过简单题目把方法论确定下来，有了方法论，后面才能应付复杂的递归。

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法!

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

好了，我们确认了递归的三要素，接下来就来练练手：

以下以前序遍历为例：

确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector在放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：

 
 
 
    
  
  
  
  1. void traversal(TreeNode* cur, vector& vec)
    2.

确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

 
 
 
    
  
  
  
  1. if (cur == NULL) return;
    2.

确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

 
 
 
    
  
  
  
  1. vec.push_back(cur->val);    // 中
    2. 
  
  
  
  2. traversal(cur->left, vec);  // 左
    3. 
  
  
  
  3. traversal(cur->right, vec); // 右
    4.

单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，在看一下完整代码：

前序遍历：

 
 
 
    
  
  
  
  1. class Solution {
    2. 
  
  
  
  2. public:
    3. 
  
  
  
  3.     void traversal(TreeNode* cur, vector& vec) {
    4. 
  
  
  
  4.         if (cur == NULL) return;
    5. 
  
  
  
  5.         vec.push_back(cur->val);    // 中
    6. 
  
  
  
  6.         traversal(cur->left, vec);  // 左
    7. 
  
  
  
  7.         traversal(cur->right, vec); // 右
    8. 
  
  
  
  8.     }
    9. 
  
  
  
  9.     vector preorderTraversal(TreeNode* root) {
    10. 
  
  
  
  10.         vector result;
    11. 
  
  
  
  11.         traversal(root, result);
    12. 
  
  
  
  12.         return result;
    13. 
  
  
  
  13.     }
    14. 
  
  
  
  14. };
    15.

那么前序遍历写出来之后，中序和后序遍历就不难理解了，代码如下：

中序遍历：

 
 
 
    
  
  
  
  1. void traversal(TreeNode* cur, vector& vec) {
    2. 
  
  
  
  2.     if (cur == NULL) return;
    3. 
  
  
  
  3.     traversal(cur->left, vec);  // 左
    4. 
  
  
  
  4.     vec.push_back(cur->val);    // 中
    5. 
  
  
  
  5.     traversal(cur->right, vec); // 右
    6. 
  
  
  
  6. }
    7.

后序遍历：

 
 
 
    
  
  
  
  1. void traversal(TreeNode* cur, vector& vec) {
    2. 
  
  
  
  2.     if (cur == NULL) return;
    3. 
  
  
  
  3.     traversal(cur->left, vec);  // 左
    4. 
  
  
  
  4.     traversal(cur->right, vec); // 右
    5. 
  
  
  
  5.     vec.push_back(cur->val);    // 中
    6. 
  
  
  
  6. }
    7.

此时大家可以做一做leetcode上三道题目，分别是：

  • 144.二叉树的前序遍历
  • 145.二叉树的后序遍历
  • 94.二叉树的中序遍历

可能有同学感觉前后中序遍历的递归太简单了，要打迭代法(非递归)，别急，我们明天打迭代法，打个通透!

其他语言版本

Java：

 
 
 
    
  
  
  
  1. // 前序遍历·递归·LC144_二叉树的前序遍历
    2. 
  
  
  
  2. class Solution {
    3. 
  
  
  
  3.     ArrayList preOrderReverse(TreeNode root) {
    4. 
  
  
  
  4.         ArrayList result = new ArrayList();
    5. 
  
  
  
  5.         preOrder(root, result);
    6. 
  
  
  
  6.         return result;
    7. 
  
  
  
  7.     }
    8. 
  
  
  
  8. 
  
  
  
  9.     void preOrder(TreeNode root, ArrayList result) {
    10. 
  
  
  
  10.         if (root == null) {
    11. 
  
  
  
  11.             return;
    12. 
  
  
  
  12.         }
    13. 
  
  
  
  13.         result.add(root.val);           // 注意这一句
    14. 
  
  
  
  14.         preOrder(root.left, result);
    15. 
  
  
  
  15.         preOrder(root.right, result);
    16. 
  
  
  
  16.     }
    17. 
  
  
  
  17. }
    18. 
  
  
  
  18. // 中序遍历·递归·LC94_二叉树的中序遍历
    19. 
  
  
  
  19. class Solution {
    20. 
  
  
  
  20.     public List inorderTraversal(TreeNode root) {
    21. 
  
  
  
  21.         List res = new ArrayList<>();
    22. 
  
  
  
  22.         inorder(root, res);
    23. 
  
  
  
  23.         return res;
    24. 
  
  
  
  24.     }
    25. 
  
  
  
  25. 
  
  
  
  26.     void inorder(TreeNode root, List list) {
    27. 
  
  
  
  27.         if (root == null) {
    28. 
  
  
  
  28.             return;
    29. 
  
  
  
  29.         }
    30. 
  
  
  
  30.         inorder(root.left, list);
    31. 
  
  
  
  31.         list.add(root.val);             // 注意这一句
    32. 
  
  
  
  32.         inorder(root.right, list);
    33. 
  
  
  
  33.     }
    34. 
  
  
  
  34. }
    35. 
  
  
  
  35. // 后序遍历·递归·LC145_二叉树的后序遍历
    36. 
  
  
  
  36. class Solution {
    37. 
  
  
  
  37.     public List postorderTraversal(TreeNode root) {
    38. 
  
  
  
  38.         List res = new ArrayList<>();
    39. 
  
  
  
  39.         postorder(root, res);
    40. 
  
  
  
  40.         return res;
    41. 
  
  
  
  41.     }
    42. 
  
  
  
  42. 
  
  
  
  43.     void postorder(TreeNode root, List list) {
    44. 
  
  
  
  44.         if (root == null) {
    45. 
  
  
  
  45.             return;
    46. 
  
  
  
  46.         }
    47. 
  
  
  
  47.         postorder(root.left, list);
    48. 
  
  
  
  48.         postorder(root.right, list);
    49. 
  
  
  
  49.         list.add(root.val);             // 注意这一句
    50. 
  
  
  
  50.     }
    51. 
  
  
  
  51. }
    52.

Python：

 
 
 
    
  
  
  
  1. # 前序遍历-递归-LC144_二叉树的前序遍历
    2. 
  
  
  
  2. class Solution:
    3. 
  
  
  
  3.     def preorderTraversal(self, root: TreeNode) -> List[int]:
    4. 
  
  
  
  4.         # 保存结果
    5. 
  
  
  
  5.         result = []
    6. 
  
  
  
  6.         
    7. 
  
  
  
  7.         def traversal(root: TreeNode):
    8. 
  
  
  
  8.             if root == None:
    9. 
  
  
  
  9.                 return
    10. 
  
  
  
  10.             result.append(root.val) # 前序
    11. 
  
  
  
  11.             traversal(root.left)    # 左
    12. 
  
  
  
  12.             traversal(root.right)   # 右
    13. 
  
  
  
  13. 
  
  
  
  14.         traversal(root)
    15. 
  
  
  
  15.         return result
    16. 
  
  
  
  16. 
  
  
  
  17. # 中序遍历-递归-LC94_二叉树的中序遍历
    18. 
  
  
  
  18. class Solution:
    19. 
  
  
  
  19.     def inorderTraversal(self, root: TreeNode) -> List[int]:
    20. 
  
  
  
  20.         result = []
    21. 
  
  
  
  21. 
  
  
  
  22.         def traversal(root: TreeNode):
    23. 
  
  
  
  23.             if root == None:
    24. 
  
  
  
  24.                 return
    25. 
  
  
  
  25.             traversal(root.left)    # 左
    26. 
  
  
  
  26.             result.append(root.val) # 中序
    27. 
  
  
  
  27.             traversal(root.right)   # 右
    28. 
  
  
  
  28. 
  
  
  
  29.         traversal(root)
    30. 
  
  
  
  30.         return result
    31. 
  
  
  
  31. 
  
  
  
  32. # 后序遍历-递归-LC145_二叉树的后序遍历
    33. 
  
  
  
  33. class Solution:
    34. 
  
  
  
  34.     def postorderTraversal(self, root: TreeNode) -> List[int]:
    35. 
  
  
  
  35.         result = []
    36. 
  
  
  
  36. 
  
  
  
  37.         def traversal(root: TreeNode):
    38. 
  
  
  
  38.             if root == None:
    39. 
  
  
  
  39.                 return
    40. 
  
  
  
  40.             traversal(root.left)    # 左
    41. 
  
  
  
  41.             traversal(root.right)   # 右
    42. 
  
  
  
  42.             result.append(root.val) # 后序
    43. 
  
  
  
  43. 
  
  
  
  44.         traversal(root)
    45. 
  
  
  
  45.         return result
    46.

网页标题：二叉树的递归遍历，套路都在这里
网站URL：http://www.csdahua.cn/qtweb/news29/45179.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

关键词优化知识

分类信息网

品牌网站建设　　 　手机网站建设公司　　 　川银永信　　 　企业网站建设　　 　做移动网站　　 　西部信息中心　　 　温江网站设计　　 　成都企业网站建设　　 　网站推广　　 　工商财税　　 　香港虚拟主机　　 　成都茶叶销售　　 　腾讯云香港空间　　 　腾讯免备案主机　　 　外贸网站设计方案　　 　眉山服务器托管　　 　java虚拟主机　　 　优化排名　　 　营销网站定位　　 　模板商城网站