首页 > 试题广场 >

二叉树的前序遍历

[编程题]二叉树的前序遍历

热度指数：126312 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

示例 1：

示例1

输入

{1,#,2,3}

输出

[1,2,3]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

咸鱼余号

public int[] preorderTraversal (TreeNode root) {
        // write code here
        if (root == null)
        {
            return new int[]{};
        }
        ArrayList<Integer> list = new ArrayList<>();
        pre(root, list);
        return list.stream().filter(integer -> integer != null).mapToInt(i->i).toArray();
    }
    public void pre (TreeNode root, ArrayList arr)
    {
        arr.add(root.val);
        if (root.left != null)
        {
            pre(root.left, arr);
        }
        if (root.right != null)
        {
            pre(root.right, arr);
        }
    }

发表于 2025-04-11 10:35:07 回复(0)

Java

牛客348570162号

public int[] preorderTraversal1 (TreeNode root) {
        if(root == null) return new int[0];
        ArrayList<Integer> list = new ArrayList<>();
        traversal(root,list);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    public void traversal(TreeNode node,ArrayList<Integer> list){
        list.add(node.val);
        if(node.left != null) traversal(node.left,list);
        if(node.right != null) traversal(node.right,list);
    }

    // 栈
    public int[] preorderTraversal (TreeNode root) {
        if(root == null) return new int[0];
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

发表于 2024-08-24 10:17:47 回复(0)

Java

人间水长东

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整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here

        // 1.初始化一个ArrayList用于动态添加数据
        ArrayList<Integer> resultList = new ArrayList<>();

        // 2.调用前序遍历递归函数
        process(resultList, root);

        // 3.将ArrayList转换成int[]并返回
        return listToArray(resultList);
    }

    // 前序遍历递归函数
    public void process(ArrayList<Integer> resultList, TreeNode root) {
        if (root== null) {
            return;
        }
        resultList.add(root.val);
        process(resultList, root.left);
        process(resultList, root.right);
    }

    // ArrayList转int[]
    public int[] listToArray(ArrayList<Integer> resultList) {
        int[] resultArray = new int[resultList.size()];
        for (int i = 0; i < resultArray.length; i++) {
            resultArray[i] = resultList.get(i);
        }
        return resultArray;
    }
}

发表于 2024-07-29 18:59:08 回复(0)

Java

你好，侦探先生

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整型一维数组
     */

    public int[] preorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> resultList = new ArrayList<Integer>();
        tran(root, resultList);

        int[] ints = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            ints[i] = resultList.get(i);
        }
        return ints;
    }

    public void tran(TreeNode root, ArrayList<Integer> resultList) {
        if (root != null) {
            resultList.add(root.val);
            tran(root.left, resultList);
            tran(root.right, resultList);
        }
    }
}

编辑于 2024-03-26 17:09:57 回复(0)

Java

不存在的神秘人

public int index=0;

public void find(TreeNode root,int[] list){

if(root==null) return;

if(root.val!=0)

list[index++]=root.val;

find(root.left,list);

find(root.right,list);

}

public int[] preorderTraversal (TreeNode root) {

// write code here

int[] intList=new int[100];

find(root,intList);

int[] list=new int[index];

for(int i=0;i<index;i++)

list[i]=intList[i];

return list;

}

编辑于 2024-03-11 16:39:06 回复(0)

Java

Fsan

发表于 2023-10-29 14:18:41 回复(0)

Java

李克雷

public class Solution {
    /**
     * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        if (null == root) {
            return new int[] {};
        }
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> numList = new ArrayList<Integer>();
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();//顶部出栈
            numList.add(root.val);//加入列表
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
        return list2Array(numList);
    }

    /**
     *  List<Integer>转化为int[]
     *
     *
     * @param nums List<Integer>类
     * @return int整型一维数组
     */
    public int[] list2Array(List<Integer> nums) {
        int[] numArray = new int[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            numArray[i] = nums.get(i);
        }
        return numArray;
    }

}

发表于 2023-10-12 11:19:06 回复(0)

Java

dqxfz

public class Solution {

int i = 0;

public int[] preorderTraversal (TreeNode root) {

int[] arr = new int[100];

recursiveIterate(arr, root);

int[] result = new int[i];

System.arraycopy(arr, 0, result, 0, i);

return result;

}

public int[] recursiveIterate(int[] arr, TreeNode node) {

if (node != null) {

arr[i++] = node.val;

recursiveIterate(arr, node.left);

recursiveIterate(arr, node.right);

}

return arr;

}

发表于 2023-09-18 20:23:22 回复(0)

Java

牛客101757813号

public int[] preorderTraversal (TreeNode root) {
        // write code here
        if(root == null){
            return new int[0];
        }
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        stack.push(root);
        while(!stack.empty()){
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        int[] result = new int[list.size()];
        for(int i = 0 ; i < list.size() ; i++){
            result[i] = list.get(i);
        }
        return result;
    }

发表于 2023-08-19 16:02:42 回复(0)

Java

菲菲菲12138

List<Integer> list=new ArrayList<Integer>();

public int[] preorderTraversal (TreeNode root) {

// write code here

dfs(root,list);

int res[]=new int[list.size()];

for(int i=0;i<list.size();i++){

res[i]= list.get(i);

}

return res;

}

public void dfs(TreeNode root,List<Integer> list){

if(root==null){

return ;

}

list.add(root.val);

dfs(root.left,list);

dfs(root.right,list);

}

发表于 2023-07-22 11:51:14 回复(0)

Java

做则必成的勇气和信心

public int[] preorderTraversal (TreeNode root) {
       //先序遍历  头左右
       List<Integer> list=new ArrayList<>();
       build(root,list);
       int[] ans=new int[list.size()];
       for(int i=0;i<list.size();i++){
        ans[i]=list.get(i);
       }
       return ans;
    }
    public void  build(TreeNode root,List<Integer> list){
        if(root==null){
            return ;
        }
        list.add(root.val);
        build(root.left,list);
        build(root.right,list);
    }

发表于 2023-07-12 11:05:02 回复(0)

Java

牛客332113879号

第19个用例，为什么会有重复的值？？

{37,-34,-48,#,-100,-100,48,#,#,#,#,-54,#,-71,-22,#,#,#,8}

用例有问题，导致hashmap(node.val -> Boolean)无法正确识别该node是否visited，因为val有重复，所以不能当作是id使用

发表于 2023-03-23 18:04:00 回复(0)

Java

一颗宏心

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 {

    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        
        preOrder(root,list);

        int[] res = new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i] = list.get(i);
        }
        return res;
    }

    public static void preOrder(TreeNode root,List<Integer> list){
        if(root!=null){
            list.add(root.val);
            preOrder(root.left,list);
            preOrder(root.right,list);
        }
    }
}

发表于 2022-12-02 23:40:58 回复(0)

Java

牛客341319853号

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整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> list = new ArrayList<>();
        preorder(list, root);
        int[] mylist = new int[list.size()];
        for(int i=0; i<list.size();i++){
            mylist[i] = list.get(i);
        }
        return mylist;
        
    }
    public void preorder(ArrayList<Integer> list, TreeNode root){
        if(root == null){
            return;
        }
        list.add(root.val);
        preorder(list,root.left);
        preorder(list,root.right);
    }
}

发表于 2022-11-13 17:34:42 回复(0)

Java

dynamo1

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整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        if (root == null) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<Integer>();
        traversal(root, list);
        int[] array = new int[list.size()];
        for(int i = 0; i< list.size();i++) {
            array[i] = list.get(i);
        }
        return array;

    }

    private void traversal(TreeNode root, List<Integer> list) {
       
        list.add(root.val);
        if(root.left != null) {
        traversal(root.left,list);
        }
         if(root.right != null) {
        traversal(root.right,list);
        }
    }


}

发表于 2022-11-04 07:40:47 回复(0)

Java

键盘都敲坏了.

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
     public int[] preorderTraversal (TreeNode root) {
        // 前序遍历: this -> left -> right
        // 存储前序遍历的结果
        List<Integer> arrayList = new ArrayList<Integer>();
        // 前序遍历
        dfs(root, arrayList);
        // 转int数组
        return arrayList.stream().mapToInt(i->i).toArray();
    }

    public void dfs(TreeNode root, List<Integer> arrayList){
        // 等于空不进行遍历
        if (root == null){
            return;
        }
        // 存储当前节点
        arrayList.add(root.val);
        // 向左子树遍历
        dfs(root.left,arrayList);
        // 向右子树遍历
        dfs(root.right,arrayList);
    }
}

发表于 2022-11-01 13:40:43 回复(0)

Java

幸福的艾伦躺平了

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整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        List list = new ArrayList<Integer>();
        preorderImpl(root,list);
        return convertIntegers(list);
        // 先根节点
        
    }
    
    public void preorderImpl(TreeNode root, List list){
               // 特殊情况
        if( root == null){
            return ;
        }
        // 将根节点的值插入到列表
        list.add(root.val);
        
        //将root的左子节点插入到list
        if(root.left != null){
            preorderImpl(root.left, list);
        }
        //将root的右子节点插入到list
        if(root.right != null){
            preorderImpl(root.right, list);
        }
        
    }
    
    public  int[] convertIntegers(List<Integer> integers)
{
    int[] ret = new int[integers.size()];
    for (int i=0; i < ret.length; i++)
    {
        ret[i] = integers.get(i).intValue();
    }
    return ret;
}


}

发表于 2022-09-14 10:56:18 回复(0)