首页 > 试题广场 >

二叉树的前序遍历

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

热度指数：102422 时间限制：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

你好，侦探先生

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)

Java

624huiguorou

递归实现：

递归进行前序遍历，由于int[]是固定长度，所以先用ArrayList来做。

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

非递归实现：（用栈实现非递归前序遍历）

public void preOrder1(TreeNode root) {
    if(root==null) return;
    // 栈，保存访问过的节点
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
    TreeNode node = root;
    while(!stack.isEmpty() || node!=null) {
        // 一直往左下遍历
        while(node!=null) {
            stack.push(node);
            nodesVal.add(node.val);
            node = node.left;
        }
        // 无左子树的时候，去判断右子树
        node = stack.pop();
        node = node.right;
    }
}

发表于 2022-09-01 13:38:42 回复(0)

Java

牛客用户007

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];
        ArrayList<Integer> res = new ArrayList();
        Stack<TreeNode> stack = new Stack();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

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

        return nums;
    }
}

发表于 2022-08-25 15:34:02 回复(0)

Java

水酥

public class Solution {

    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList();
        preorder(root, list);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    public void preorder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        list.add(root.val);
        preorder(root.left, list);
        preorder(root.right, list);
    }
}

发表于 2022-08-15 16:51:15 回复(0)