NC45 实现二叉树先序，中序和后序遍历

题目链接：https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362

题目描述

给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。

数据范围：0≤n≤1000，树上每个节点的val值满足 0≤val≤100

要求：空间复杂度 O(n)，时间复杂度 O(n)

样例解释：

示例 1：

输入：{1,2,3}
返回值：[[1,2,3],[2,1,3],[2,3,1]]
说明：如题面图

示例 2：

输入：{}
返回值：[[],[],[]]

解题代码

import java.util.*;
import java.util.ArrayList;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    //先序遍历存储数组
    public ArrayList<Integer> first = new ArrayList<>();
    //中序遍历存储数组
    public ArrayList<Integer> middle = new ArrayList<>();
    //后续遍历存储数组
    public ArrayList<Integer> later = new ArrayList<>();   
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders(TreeNode root) {
        // write code here
        //关键点
        //1.确定存储数组大小 OR 使用 ArrayList
        //2.前中后遍历算法
        //3.ArrayList 数组转 int[] 数组方法
        firstOrder(root);
        middleOrder(root);
        laterOrder(root);
        int[][] result = new int[3][first.size()];
        result[0] = toIntArray(first);
        result[1] = toIntArray(middle);
        result[2] = toIntArray(later);
        return result;
    }   
    //ArrayList 转 int[]
    public int[] toIntArray(ArrayList<Integer> list) {
        if (list == null || list.size() < 1) {
            return new int[0];
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }   
    //先序遍历
    public void firstOrder(TreeNode root) {
        //跳出条件
        if (root == null) {
            return;
        }
        first.add(root.val);
        firstOrder(root.left);
        firstOrder(root.right);
    }   
    //中序遍历
    public void middleOrder(TreeNode root) {
        //跳出条件
        if (root == null) {
            return;
        }
        middleOrder(root.left);
        middle.add(root.val);
        middleOrder(root.right);
    }   
    //后序遍历
    public void laterOrder(TreeNode root) {
        //跳出条件
        if (root == null) {
            return;
        }
        laterOrder(root.left);
        laterOrder(root.right);
        later.add(root.val);
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请...
最后编辑时间为: 2022/07/10 21:10:42