二叉树的遍历方式(递归)

╰+攻爆jí腚メ 2023-09-28 15:34 54阅读 0赞

#

  • 前序遍历
    • 思路
    • 图示
    • 代码
  • 中序遍历
    • 思路
    • 代码
  • 后序遍历
    • 思路
    • 代码

前序遍历

二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
在这里插入图片描述

思路

  • 递归需要考虑三个要素
  • 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  • 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  • 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
  • 前序遍历，其实就是先访问根节点，然后访问左子树，再访问右子树

图示

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码

  1. //递归
  2. class Solution {
  4.     public List<Integer> preorderTraversal(TreeNode root) {
  6.         List<Integer> list=new ArrayList<>();
  7.         preorder(root,list);
  8.         return list;
  10.     }
  11.     public void preorder(TreeNode root,List list){
  13.         if(root == null) return ;
  14.         list.add(root.val);
  15.         preorder(root.left,list);
  16.         preorder(root.right,list);
  18.     }
  19. }

中序遍历


二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
在这里插入图片描述

思路

  • 左子树–>根节点–>右子树

代码

  1. class Solution {
  3.     public List<Integer> inorderTraversal(TreeNode root) {
  5.         List<Integer> list=new ArrayList<>();
  6.         inorder(root,list);
  7.         return list;
  9.     }
  11.     public void inorder(TreeNode root,List<Integer> res){
  13.         if(root==null) return;
  14.         inorder(root.left,res);
  15.         res.add(root.val);
  16.         inorder(root.right,res);
  17.     }
  23. }

后序遍历

思路

  • 左子树–>右子树–>根节点

代码

  1. class Solution {
  3.     List<Integer> list;
  4.     public List<Integer> postorderTraversal(TreeNode root) {
  6.         list=new ArrayList();
  7.         postorder(root);
  8.         return list;
  9.     }
  10.     public void postorder(TreeNode root){
  12.         if(root==null) return ;
  13.         postorder(root.left);
  14.         postorder(root.right);
  15.         list.add(root.val);
  16.     }
  17. }

发表评论

表情：
评论列表 （有 0 条评论，54人围观）

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

相关阅读

    相关 递归遍历二叉树

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

    今天药忘吃喽~今天药忘吃喽~/ 0 赞/ 121 阅读

    相关 二叉树遍历（递归）

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

    末蓝、末蓝、/ 0 赞/ 286 阅读