二叉树的递归遍历

ゞ 浴缸里的玫瑰 2023-10-14 21:13 155阅读 0赞

二叉树的递归遍历

  • 三步分析方法
      1. 确定递归函数的参数和返回值
      1. 确定终止条件
      1. 确定单层递归的逻辑
  • 递归实现的底层机制
  • 代码实现
      1. 前序遍历
      1. 中序遍历
      1. 后序遍历

三步分析方法

  1. 确定递归函数的参数和返回值
  2. 确定终止条件
  3. 确定单层递归的逻辑

1. 确定递归函数的参数和返回值

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

2. 确定终止条件

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

3. 确定单层递归的逻辑

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

递归实现的底层机制

递归实现的底层是使用栈

代码实现

1. 前序遍历

  1. // 前序遍历·递归·LC144_二叉树的前序遍历
  2. class Solution {
  3. public List<Integer> preorderTraversal(TreeNode root) {
  4. List<Integer> result = new ArrayList<Integer>();
  5. preorder(root, result);
  6. return result;
  7. }
  8. public void preorder(TreeNode root, List<Integer> result) {
  9. if (root == null) {
  10. return;
  11. }
  12. result.add(root.val);
  13. preorder(root.left, result);
  14. preorder(root.right, result);
  15. }
  16. }

2. 中序遍历

  1. // 中序遍历·递归·LC94_二叉树的中序遍历
  2. class Solution {
  3. public List<Integer> inorderTraversal(TreeNode root) {
  4. List<Integer> res = new ArrayList<>();
  5. inorder(root, res);
  6. return res;
  7. }
  8. void inorder(TreeNode root, List<Integer> list) {
  9. if (root == null) {
  10. return;
  11. }
  12. inorder(root.left, list);
  13. list.add(root.val); // 注意这一句
  14. inorder(root.right, list);
  15. }
  16. }

3. 后序遍历

  1. // 后序遍历·递归·LC145_二叉树的后序遍历
  2. class Solution {
  3. public List<Integer> postorderTraversal(TreeNode root) {
  4. List<Integer> res = new ArrayList<>();
  5. postorder(root, res);
  6. return res;
  7. }
  8. void postorder(TreeNode root, List<Integer> list) {
  9. if (root == null) {
  10. return;
  11. }
  12. postorder(root.left, list);
  13. postorder(root.right, list);
  14. list.add(root.val); // 注意这一句
  15. }
  16. }

参考资料:二叉树的递归遍历

发表评论

表情:
评论列表 (有 0 条评论,155人围观)

还没有评论,来说两句吧...

相关阅读

    相关

    网上的递归遍历代码很多,这里就不赘述了,说一下思考的角度: 1. 把每一个棵子树都看成是独立的树; 2. 每一个节点都会把递归的代码重新执行一次; 3. 想象压栈的过程

    相关

    二叉树又称为红黑树,是一种常用的数据结构,而二叉树的遍历则是一种非常基本的操作。遍历二叉树的方式有两大类:递归和非递归。递归方式算法较为简便,并且更便于理解,非递归方式则需要对