首页 > 试题广场 >

二叉树的前序遍历

[编程题]二叉树的前序遍历
  • 热度指数：103130 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

数据范围：二叉树的节点数量满足 ，二叉树节点的值满足 ，树的各节点的值各不相同

示例 1：


示例1

输入

{1,#,2,3}

输出

[1,2,3]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Go
determination66头像 determination66
// 前序遍历，最简单的可以递归
func preorderTraversal(root *TreeNode) []int {
    // write code here
    var res []int
    preorderTraversalHelper(root, &res)
    return res
}
// 辅助类
func preorderTraversalHelper(root *TreeNode, res *[]int) {
    if root != nil {
        *res = append(*res, root.Val)
        preorderTraversalHelper(root.Left, res)
        preorderTraversalHelper(root.Right, res)
    }
}
发表于 2023-11-23 10:17:40 回复(0)
Go
zipman头像 zipman
morris先序求解 
func preorderTraversal(root *TreeNode) []int {
    res:=make([]int,0)
	cur, mostRight := root, &TreeNode{}
	for cur != nil {
		mostRight = cur.Left
		if mostRight != nil {
			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			if mostRight.Right != cur {
				res = append(res, cur.Val)
				mostRight.Right = cur
				cur = cur.Left
				continue
			} else {
				mostRight.Right = nil
			}
		}else{
            res = append(res, cur.Val)
        }
		cur = cur.Right
	}
    return res
}


发表于 2023-01-12 18:30:43 回复(0)
Go
牛客45680046号头像 牛客45680046号

func preorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)

    // return preorder1(root, res)
    // return preorder2(root, res)
    return preorder3(root, res)
}

func preorder1(root *TreeNode, nums []int) []int {
    if root != nil {
        nums = append(nums, root.Val)
        nums = preorder1(root.Left, nums)
        nums = preorder1(root.Right, nums)
    }
    return nums
}

func preorder2(root *TreeNode, nums []int) []int {
    if root == nil {
        return nums
    }

    stack := list.New()
    stack.PushBack(root)
    p := root
    for stack.Len() != 0 {
        p = stack.Remove(stack.Back()).(*TreeNode)
        nums = append(nums, p.Val)
        if p.Right != nil {
            stack.PushBack(p.Right)
        }
        if p.Left != nil {
            stack.PushBack(p.Left)
        }
    }

    return nums
}

func preorder3(root *TreeNode, nums []int) []int {
    if root == nil {
        return nums
    }

    stack := list.New()
    p := root
    for stack.Len() != 0 || p != nil {
        for p != nil {
            nums = append(nums, p.Val)
            stack.PushBack(p)
            p = p.Left
        }
        p = stack.Remove(stack.Back()).(*TreeNode)
        p = p.Right
    }

    return nums
}
发表于 2022-11-27 15:36:32 回复(0)
Go
木名V头像 木名V 
package main
// import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
*/

var res = []int{}

func preorderTraversal( root *TreeNode ) []int {
    // 方法1：遍历的思维模式
    // 通过遍历一遍二叉树得到答案。用一个 traverse 函数配合外部变量来实现。
    traverse(root)
    return res
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    res = append(res, root.Val)
    traverse(root.Left)
    traverse(root.Right)
}

发表于 2022-11-17 12:35:45 回复(0)
Go
风轻云淡.头像 风轻云淡. 
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)
Go
admxt头像 admxt
package main
// import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
*/
func preorderTraversal( root *TreeNode ) []int {
    // write code here
    ret:=[]int{}
    if root==nil{
        return ret
    }else{
        ret=append(ret,root.Val)
        ret=append(ret,preorderTraversal(root.Left)...)
        ret=append(ret,preorderTraversal(root.Right)...)
        return ret
    }
}
发表于 2022-03-31 10:51:43 回复(0)
提交观点

问题信息

树 dfs 递归 广度优先搜索(BFS)
难度：
6条回答 5392浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号