⭐️二叉树的前中后序遍历⭐️

🔐题目详情

前序遍历

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

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

示例 1：

示例1

输入：

{1,#,2,3}

返回值：

[1,2,3]

中序遍历

给定一个二叉树的根节点root，返回它的中序遍历结果。

数据范围：树上节点数满足0≤n≤1000，树上每个节点的值满足 −1000≤val≤1000
进阶：空间复杂度 O*(n)，时间复杂度 O(n)

示例1

输入：

{1,2,#,#,3}

返回值：

[2,3,1]

说明：

示例2

输入：

{}

返回值：

[]

示例3

输入：

{1,2}

返回值：

[2,1]

说明：

示例4

输入：

{1,#,2}

返回值：

[1,2]

说明：

备注：

树中节点数目在范围 [0, 100] 内
树中的节点的值在[-100,100]以内

后序遍历

给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

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

样例图

示例1

输入：

{1,#,2,3}

返回值：

[3,2,1]

说明：

如题面图  

示例2

输入：

{1}

返回值：

[1]

题目链接：二叉树的前中后序遍历

题目链接：二叉树的中序遍历

题目链接：二叉树的后序遍历

💡解题思路

所谓前序遍历，也叫做先序遍历，是按照二叉树搜索路径先获取根结点数据，再获取左子树数据，最后获取右子树数据。

前序遍历三部曲：

1. 访问根结点；
2. 前序遍历左子树；
3. 前序遍历右子树。

如下图这样一棵二叉树：

前序遍历的顺序是： $A->B->D->G->C->E->F$

递归实现：
递归条件：如果结点root为空，则返回。
(1)获取并保存根结点数据。
(2)前序遍历左子树，并保存结果。
(3)前序遍历右子树，并保存结果。

所谓中序遍历，就是按照二叉树搜索路径先获取左子树数据，再获取根结点数据，最后获取右子树数据。

中序遍历三部曲：

1. 中序遍历左子树；
2. 访问根结点；
3. 中序遍历右子树。

如下图这样一棵二叉树：

中序遍历的顺序是： $D->G->B->A->E->C->F$

递归实现：
递归条件：如果结点root为空，则返回。
(1)中序遍历左子树，并保存结果。
(2)获取并保存根结点数据。
(3)中序遍历右子树，并保存结果。

所谓后序遍历，就是按照二叉树搜索路径先获取右子树数据，再获取右子树数据，最后获取根结点数据。

后序遍历三部曲：

1. 后序遍历左子树；
2. 后序遍历右子树；
3. 访问根结点。

如下图这样一棵二叉树：

后序遍历的顺序是： $G->D->B->E->F->C->A$

递归实现：
递归条件：如果结点root为空，则返回。
(1)后序遍历左子树，并保存结果。
(2)后序遍历右子树，并保存结果。
(3)获取并保存根结点数据。

🔑源代码

前序遍历：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    private List<Integer> list = new ArrayList<>();
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        dfs(root);
        int[] ans = new int[list.size()];
        int i = 0;
        for (int x : list) {
            ans[i++] = x;
        }
        return ans;
    }
    private void dfs(TreeNode root) {
        if (root == null) return;

        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}

中序遍历：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */

    private List<Integer> list = new ArrayList<>();
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        dfs(root);
        int[] ans = new int[list.size()];
        int i = 0;
        for (int x : list) {
            ans[i++] = x;
        }
        return ans;
    }
    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}

后序遍历：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    private List<Integer> list = new ArrayList<>();
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        dfs(root);
        int[] ans = new int[list.size()];
        int i = 0;
        for (int x : list) {
            ans[i++] = x;
        }
        return ans;
    }
    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        dfs(root.right);
        list.add(root.val);
    }
}

🌱总结

⭐️层序遍历⭐️

🔐题目详情

描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]

]

提示:

0 <= 二叉树的结点数 <= 1500

示例1

输入：

{1,2}

返回值：

[[1],[2]]

示例2

输入：

{1,2,3,4,#,#,5}

返回值：

[[1],[2,3],[4,5]]

题目链接：求二叉树的层序遍历

💡解题思路

对于二叉树的层序遍历，它的实现思路与判断一棵二叉树是否是完全二叉树思路十分相似，都是使用队列来进行实现，但是入队时有一点不同，那就是如果结点为空，则不需要入队，直到最终队列和当前结点均为空时，表示遍历结束。

对于上面这道题，层序遍历还需要将每层的元素分开，单独存入List中，为了解决这个问题，可以在每次获取出队元素前，先获取队列中元素个数，这个元素个数就是当前层次的元素个数，这样就能把每层的元素都分开了。
（1）记录当前队列元素个数，即二叉树每层的元素个数。
（2）将此层二叉树的结点的左右非空孩子结点存于队列中，并将该层二叉树结点的值存于顺序表中。
（3）将非空的子结点存入队列中。

🔑源代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            ans.add(list);
        }
        return ans;
    }
}