【算法合集】学习算法第三天（二叉树遍历篇）

桃扇骨 2024-05-23 18:59 63阅读 0赞

> ✅?个人主页：[程序猿追][Link 1]
> 
> ✅?系列专栏：[算法合集][Link 2]
> 
> ✅?目前状态：创建Java学习之路（零基础到就业实战）系列，目前更新到JAVAWEB开发
> 
> ✅?作者简介：大家好，我是程序猿追，全栈领域新星创作者，算法爱好者，常在作者周榜排名前30，某不知名的 ACMer
> 
> ✅?推荐一款刷题面试找工作三不误的网站——[牛客网][Link 3]
> 
> ✅?个人名言：不积跬步无以至千里，趁年轻，使劲拼，给未来的自己一个交代！

**目录**

二叉树的前序遍历

题解代码

二叉树的中序遍历

题解代码

二叉树的后序遍历

题解代码

求二叉树的层序遍历

题解代码

--------------------

## 二叉树的前序遍历 ##

> **描述**
> 
> 给你二叉树的根节点 root ，返回它节点值的 前序遍历。
> 
> 数据范围：二叉树的节点数量满足 0≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同

> 示例1：
> 
> ![632526253f35454e918e1d334d757560.png][]

> **输入：**
> 
>     {1,#,2,3}
> 
> **返回值：**
> 
>     [1,2,3]

### 题解代码 ###

import java.util.*;
    public class Solution {
        public void preorder(List<Integer> list, TreeNode root){
            //遇到空节点则返回 fast-template
            if(root == null)
                return;
            //先遍历根节点
            list.add(root.val);
            //再去左子树
            preorder(list, root.left);
            //最后去右子树
            preorder(list, root.right);
        }
        public int[] preorderTraversal (TreeNode root) {
            //添加遍历结果的数组
            List<Integer> list = new ArrayList();
            //递归前序遍历
            preorder(list, root);
            //返回的结果
            int[] res = new int[list.size()];
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;}
    }

## 二叉树的中序遍历 ##

> **描述**
> 
> 给定一个二叉树的根节点root，返回它的中序遍历结果。
> 
> 数据范围：树上节点数满足0≤n≤1000，树上每个节点的值满足 0≤val≤1000  
> 进阶：空间复杂度 O(n)，时间复杂度 O(n)

**示例1**

> **输入：**
> 
>     {1,2,#,#,3}
> 
> **返回值：**
> 
>     [2,3,1]
> 
> 说明：

> 示例2
> 
> **输入：**
> 
> \{\}
> 
> **返回值：**
> 
> \[\]
> 
> 示例3
> 
> **输入：**
> 
> \{1,2\}
> 
> **返回值：**
> 
> \[2,1\]
> 
> **说明：**
> 
> 示例4
> 
> **输入：**
> 
> \{1,\#,2\}
> 
> **返回值：**
> 
> \[1,2\]

### 题解代码 ###

import java.util.*;
    public class Solution {
        public void inorder(List<Integer> list, TreeNode root){
            //遇到空节点则返回 fast-template
            if(root == null)
                return;
            //先去左子树
            inorder(list, root.left);
            //再访问根节点
            list.add(root.val);
            //最后去右子树
            inorder(list, root.right);
        }
        public int[] inorderTraversal (TreeNode root) {
             //添加遍历结果的数组
            List<Integer> list = new ArrayList();
            //递归中序遍历
            inorder(list, root);
            //返回的结果
            int[] res = new int[list.size()];
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;}
    }

## 二叉树的后序遍历 ##

> **描述**
> 
> 给定一个二叉树，返回他的后序遍历的序列。
> 
> 后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
> 
> 数据范围：二叉树的节点数量满足0≤n≤100 ，二叉树节点的值满足 11≤val≤100 ，树的各节点的值各不相同
> 
> **样例图**
> 
> ![6ea92b9215cb4ba89da209a4765f7578.png][]
> 
> 示例1
> 
> **输入：**
> 
>     {1,#,2,3}
> 
> **返回值：**
> 
>     [3,2,1]
> 
> **说明：**
> 
>     如题面图
> 
> 示例2
> 
> **输入：**
> 
>     {1}
> 
> **返回值：**
> 
>     [1]

### 题解代码 ###

import java.util.*;
    public class Solution {
        public void postorder(List<Integer> list, TreeNode root){
            //遇到空节点则返回 fast-template
            if(root == null)
                return;
             //先去左子树
            postorder(list, root.left);
            //再去右子树
            postorder(list, root.right);
            //最后访问根节点
            list.add(root.val);
        }
        public int[] postorderTraversal (TreeNode root) {
            //添加遍历结果的数组
            List<Integer> list = new ArrayList();
            //递归后序遍历
            postorder(list, root);
            //返回的结果
            int[] res = new int[list.size()];
            for(int i = 0; i < list.size(); i++)
                res[i] = list.get(i);
            return res;}
    }

## 求二叉树的层序遍历 ##

描述

> 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）  
> 例如：  
> 给定的二叉树是\{3,9,20,\#,\#,15,7\},  
> ![29e445f5bb70484eaaa9ec06409f246d.png][]  
> 该二叉树层序遍历的结果是  
> \[  
> \[3\],  
> \[9,20\],  
> \[15,7\]
> 
> \]
> 
> 数据范围：二叉树的节点数满足 1≤n≤105
> 
> 示例1
> 
> **输入：**
> 
> \{1,2\}  
> **返回值：**  
> \[\[1\],\[2\]\]
> 
> 示例2
> 
> **输入：**
> 
> \{1,2,3,4,\#,\#,5\}
> 
> **返回值：**
> 
> \[\[1\],\[2,3\],\[4,5\]\]

### 题解代码 ###

import java.util.*;
    public class Solution {
        public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
            ArrayList<ArrayList<Integer> > res = new ArrayList();
            if(root == null)
                //如果是空，则直接返回空数组 fast-template
                return res;
            //队列存储，进行层次遍历
            Queue<TreeNode> q = new ArrayDeque<TreeNode>();
            q.add(root);
            while(!q.isEmpty()){
                //记录二叉树的某一行
                ArrayList<Integer> row = new ArrayList();
                int n = q.size();
                //因先进入的是根节点，故每层结点多少，队列大小就是多少
                for(int i = 0; i < n; i++){
                    TreeNode cur = q.poll();
                    row.add(cur.val);
                    //若是左右孩子存在，则存入左右孩子作为下一个层次
                    if(cur.left != null)
                        q.add(cur.left);
                    if(cur.right != null)
                        q.add(cur.right);
                }
                //每一层加入输出
                res.add(row);
            }
            return res;}
    }

> 算法对程序员来说及其重要，语言和开发平台不断变化，但是万变不离其宗的是那些算法和理论，依稀记得我那个玩的很好的一个学长（在大二就拿到了 offer），他告诉我想找一个好的工作，那刷题一定是必不可少的
> 
> 现在算法刷题平台还是蛮多的，给大家介绍一个我认为与大厂关联最深的平台——[牛客网][Link 3]

[Link 1]: https://blog.csdn.net/aasd23?spm=1000.2115.3001.5343
[Link 2]: https://blog.csdn.net/aasd23/category_11805404.html?spm=1001.2014.3001.5482
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_cxyz_sf
[632526253f35454e918e1d334d757560.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/23/731b08317fba48e7b45900f1fc9b8a1f.png
[6ea92b9215cb4ba89da209a4765f7578.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/23/2ba620980c8d4a1a80f9df57e5037e31.png
[29e445f5bb70484eaaa9ec06409f246d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/23/ece9da99999948f69f36e6692a65d619.png