135-1821-9792

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

二叉树的递归遍历

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

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

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

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

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

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

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

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

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

以下以前序遍历为例：

确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入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://wtcwzsj.com/article/cdohgje.html

其他资讯


关于我们
我们的服务
网站建设案例
新闻动态
联系我们

135-1821-9792

公司服务热线
友情链接： 班戈网站建设公司   手机软件开发   社区广告牌制作   成都西信机房   眉山发电机公司   四川发电机维保   成都柴油发电机租赁   保温橡塑管   成都发电机组销售   渠县网站制作   

Copyright © 2009-2022 www.wtcwzsj.com 青羊区广皓图文设计工作室（个体工商户） 版权所有　蜀ICP备19037934号