网络知识 娱乐 【算法合集】学习算法第三天(二叉树遍历篇)

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

✅🎡个人主页:程序猿追

✅🎡系列专栏:算法合集

✅🎡目前状态:创建Java学习之路(零基础到就业实战)系列,目前更新到JAVAWEB开发

✅🎡作者简介:大家好,我是程序猿追,全栈领域新星创作者,算法爱好者,常在作者周榜排名前30,某不知名的 ACMer

✅🎡推荐一款刷题面试找工作三不误的网站——牛客网

✅🎡个人名言:不积跬步无以至千里,趁年轻,使劲拼,给未来的自己一个交代!

目录

二叉树的前序遍历

题解代码

二叉树的中序遍历

 题解代码

二叉树的后序遍历

题解代码

求二叉树的层序遍历

题解代码


二叉树的前序遍历

描述

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

数据范围:二叉树的节点数量满足 0≤n≤100  ,二叉树节点的值满足1≤val≤100  ,树的各节点的值各不相同

示例1: 

输入:

{1,#,2,3}

返回值:

[1,2,3]

题解代码

import java.util.*;
public class Solution {
    public void preorder(List 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 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 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 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  ,树的各节点的值各不相同

样例图

示例1

输入:

{1,#,2,3}

返回值:

[3,2,1]

说明:

如题面图   

示例2

输入:

{1}

返回值:

[1]

题解代码

import java.util.*;
public class Solution {
    public void postorder(List 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 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},

该二叉树层序遍历的结果是
[
[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> levelOrder (TreeNode root) {
        ArrayList<ArrayList > res = new ArrayList();
        if(root == null)
            //如果是空,则直接返回空数组 fast-template
            return res;
        //队列存储,进行层次遍历
        Queue q = new ArrayDeque();
        q.add(root);
        while(!q.isEmpty()){
            //记录二叉树的某一行
            ArrayList 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),他告诉我想找一个好的工作,那刷题一定是必不可少的

现在算法刷题平台还是蛮多的,给大家介绍一个我认为与大厂关联最深的平台——牛客网