首页 > 试题广场 >

二叉树的前序遍历

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

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

陈让然

方法一：递归
#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)

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)

StellarVibes

void fuc(struct TreeNode* root, int* arr,int * count)

{

if (root == NULL)

{

return;

}

arr[*count] = root->val;

//printf("%d ",arr[*count]);

//printf("%d\n",*count);

(*count)++;

fuc(root->left, arr,count);

fuc(root->right, arr,count);

}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {

int* arr = (int*)malloc(sizeof(4)*1000);

int count = 0;

fuc(root, arr,&count);

//while(*arr)

//{

//printf("%d ",*arr);

//arr++;

//}

*returnSize=count;

return arr;

}

发表于 2024-12-14 18:24:57 回复(1)

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)

牛客30511778号

class Solution:
    def preorderTraversal(self , root ):
        # write code here
        if not root:return [] 
        sys.setrecursionlimit(1500)
        return  [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

发表于 2024-06-29 10:54:19 回复(0)

PeterLee6688

先序==》中间，左边，右边。所以中间的直接拿出来，再看左边和右边，都是到最底层为空直接返回

func preorderTraversal( root *TreeNode ) []int {
    // write code here
    var res []int
    peorder(&res, root)
   return res
}
func peorder(res *[]int, root *TreeNode){
    if root == nil{
        return
    }
    *res = append(*res, root.Val)
    peorder(res, root.Left)
    peorder(res, root.Right)
}

发表于 2024-05-19 11:33:52 回复(0)

一个优雅的程序猿

void preorderTraver(struct TreeNode* root, int* res, int* StaticReturnSize ) {
    res[(*StaticReturnSize)++] = root->val;
    if(root->left!=NULL) 
        preorderTraver(root->left, res, StaticReturnSize);
    if(root->right!=NULL) 
        preorderTraver(root->right, res, StaticReturnSize);
}    
int* preorderTraversal(struct TreeNode* root, int* returnSize ) {
    static int res[100]={0}, StaticReturnSize=0;
    if(root==NULL) 
        return NULL;
    preorderTraver(root, res, &StaticReturnSize);
    *returnSize = StaticReturnSize;
    return res;
}

编辑于 2024-03-16 15:55:35 回复(0)

Python3

tkds

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

发表于 2024-01-08 16:02:39 回复(0)

飞高高咯

吐槽：n>=1

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

Python3

佳人_

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        self.preorderTraversalRecursive(root, result)
        return result

    def preorderTraversalRecursive(self, node, result):
        if not node:
            return

        # 访问当前节点的值
        result.append(node.val)

        # 递归遍历左子树
        self.preorderTraversalRecursive(node.left, result)

        # 递归遍历右子树
        self.preorderTraversalRecursive(node.right, result)

发表于 2023-11-14 18:53:49 回复(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)

yaaaa_

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)