首页 > 试题广场 >

二叉树的前序遍历

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

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

sout"勇敢牛牛"

简单题我重拳出击

public class Solution {

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

    public int[] preorderTraversal (TreeNode root) {
        List<Integer> list = preOrder(root);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    List<Integer> preOrder(TreeNode node) {
        if (node == null) {
            return list;
        }
        list.add(node.val);
        preOrder(node.left);
        preOrder(node.right);
        return list;
    }
}

发表于 2022-03-01 09:50:52 回复(0)

Python3

来个offer给个机会

极简代码

class Solution:
    def preorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        if not root:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

发表于 2022-11-05 00:07:23 回复(0)

C++

auheijil

class Solution {
public:
    vector<int> ret;
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return ret;
        ret.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return ret;
    }
};

发表于 2022-03-26 12:55:23 回复(2)

Chromium丶

static int count = 0;
void preOrder(struct TreeNode *root,int *a){
    if(root != NULL){
        a[count++] = root->val;
        preOrder(root->left, a);
        preOrder(root->right, a);
    }
}


int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    int *a = (int*)malloc(sizeof(int)*101);
    preOrder(root, a);
    *returnSize = count;
    return a;
}

发表于 2022-03-17 16:12:04 回复(3)

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)

Python3

Crazycabbage_

class Solution:
    l = []
    def preorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        if root == None:
            return 
        self.l.append(root.val)
        self.preorderTraversal(root.left)
        self.preorderTraversal(root.right)
        return self.l

发表于 2022-06-25 18:51:12 回复(0)

风轻云淡.

func preorderTraversal( root *TreeNode ) []int {
    // write code here
    arr:=make([]int,0)
    var dfs func(root *TreeNode)
    dfs=func(root *TreeNode){
        if root==nil{
            return
        }
        arr=append(arr,root.Val)
        dfs(root.Left)
        dfs(root.Right)
    }
    dfs(root)
    return arr
}

发表于 2022-04-28 16:16:04 回复(1)

C++

牛娃牛娃

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    void traversal(TreeNode* cur,vector<int>&vec){
        if(cur==nullptr)return;
        vec.push_back(cur->val);
        traversal(cur->left,vec);
        traversal(cur->right,vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root,res);
        return res;
    }

};

发表于 2022-04-27 17:56:43 回复(0)

Javascript

没有实习的鱼

function preorderTraversal( root ) {
    // write code here
    var node=root
    var result=[]
    var preorderTraversalNode=function(node,result){
        if(node!==null){
            result.push(parseInt(node.val))
            preorderTraversalNode(node.left,result)
            preorderTraversalNode(node.right,result)
        }
    }
    preorderTraversalNode(node,result)
    return result
}

发表于 2022-04-20 19:45:25 回复(0)

Java

闪金镇猎人

public int[] preorderTraversal(TreeNode root) {
  List<Integer> list = new ArrayList<>();
  if (root != null) {
    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);
    }
  }

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

发表于 2022-03-07 00:56:23 回复(0)

飞高高咯

吐槽：n>=1

发表于 2023-11-18 21:14:44 回复(0)

陈让然

方法一：递归
#include <stdio.h> #include <stdlib.h> //记录结点个数 int count=0; //存储结点值，方便返回 int arr[101]; //先根后左右 void preOrder(struct TreeNode*root,int*arr) { if(root) { arr[count++]=root->val; preOrder(root->left, arr); preOrder(root->right, arr); } } int* preorderTraversal(struct TreeNode* root, int* returnSize ) { // write code here preOrder(root, arr); //便利侯，关系结点数量 *returnSize=count; return arr; }

方法二：栈实现，按先序顺序先入栈结点，直到无左结点，再出栈，对右节点遍历

#include <stdio.h> #include <stdlib.h> struct TreeNode* stack[100]; //作为栈使用，栈底是下标0 int stack_top = -1; //入栈 void push(struct TreeNode* node) { stack[++stack_top] = node; } //出栈 struct TreeNode* pop() { return stack[stack_top--]; } //先序遍历根->左->右 //用栈实现，先进后出 int* preorderTraversal(struct TreeNode* root, int* returnSize) { if (!root) { *returnSize = 0; return NULL; } int* ret_arr = malloc(sizeof(int) * 100); int i = 0; while (root || stack_top != -1) { //从根节点开始 while (root) { //根节点存在，保存val ret_arr[i++] = root->val; //每个根节点入栈 push(root); //根节点左移，也就是每次先将左值保存 //无左结点，跳出对右节点操作 root = root->left; } //根节点等于栈顶元素，即上一个无左结点的节点 root = pop(); //开始遍历右节点 root = root->right; } *returnSize = i; return ret_arr; }

发表于 2023-09-17 15:39:07 回复(0)

FLYFREELY

二叉树的前序遍历，即根左右，可以用递归遍历的方法完成

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        vector<int> res;
        preOrder(res, root);
        return res;
    }
    void preOrder(vector<int> &res, TreeNode *root) { //传入数组的引用，根结点的指针
        if (root == nullptr) return;
        res.push_back(root->val);
        preOrder(res, root->left); //递归遍历
        preOrder(res, root->right);
    }
};

发表于 2023-08-13 14:52:25 回复(0)

慕尘_

function preorderTraversal( root ) {
    let res = []
    const dfs = (root)=>{
        if(!root) return
        res.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    return res
}

发表于 2023-07-19 11:44:59 回复(0)

C++

爱吃肉的咸鱼在春招

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> vec;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root!=NULL){
            this->vec.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return this->vec;
    }
};

发表于 2023-04-29 18:23:02 回复(0)

TypeScript

神奇的小白离上岸不远了

export function preorderTraversal(root: TreeNode): number[] {
    // write code here 非递归，利用栈
    let stack: TreeNode[] = root ? [root] : [];
    let nums = [];
    let temp: TreeNode = null;
    while (stack.length > 0) {
        temp = stack.pop();
        nums.push(temp.val);
        if (temp.right) stack.push(temp.right);
        if (temp.left) stack.push(temp.left);
    }
    return nums;
}

发表于 2023-02-17 17:54:50 回复(0)

C++

Spectre_

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> preorderTraversal(TreeNode* root) {
        // 时间复杂度O(N)，空间复杂度O(N)
        vector<int> res;
        if (root == nullptr) return res;
        stack<TreeNode*> stk;
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            res.push_back(node->val);
            if (node->right) stk.push(node->right);
            if (node->left) stk.push(node->left);
        }
        return res;
    }
};

发表于 2022-10-09 10:33:25 回复(0)

JavaScript Node

牛客79522169号

function preorderTraversal(root) {
  // write code here
  let result = [];
  if (root) {
    result.push(root.val);
    result.push(...preorderTraversal(root.left));
    result.push(...preorderTraversal(root.right));
  }
  return result;
}

发表于 2022-09-27 15:22:06 回复(0)

JackBella

using System;
using System.Collections.Generic;
class Solution {
    public List<int> preorderTraversal (TreeNode root) {
        List<int> list = new List<int>();
        list = Traversal(list, root);
        return list;
    }
    public static List<int> Traversal(List<int> list , TreeNode root)
    {
        if(root == null) return list;
        list.Add(root.val);
        list = Traversal(list, root.left);
        list = Traversal(list, root.right);
        return list;
    }
}

发表于 2022-07-22 14:13:32 回复(0)

一个fw狗

int preorder(struct TreeNode*root ,int*arr){
    static int count=0;//定义一个在堆上创建的变量，用来记录遍历元素个数
    if(root!=NULL){
        arr[count++]=root->val;
        preorder(root->left,arr);
        preorder(root->right,arr);
    }
    return count;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    int *arr=malloc(sizeof(int)*101);
    *returnSize=preorder(root,arr);
    return arr;
}

发表于 2022-03-23 19:15:05 回复(0)