题解 | #二叉树的前序遍历#

二叉树的前序遍历

http://www.nowcoder.com/practice/5e2135f4d2b14eb8a5b06fab4c938635

二叉树的前序遍历

题目描述 给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

方法一:python方法

解题思路

对于本题,前序遍历就是一个递归,直接套模板,使用python实现。

alt

解题代码

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

复杂度分析

时间复杂度:使用递归,因此时间复杂度为O(n)O(n)

空间复杂度:使用递归,递归栈使用内存地址空间,因此空间复杂度为O(n)O(n)

方法二:golang方法

解题思路

思路同方法一,使用golang实现。

解题代码

package main
import . "nc_tools"

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

复杂度分析

时间复杂度:使用递归,因此时间复杂度为O(n)O(n)

空间复杂度:使用递归,递归栈使用内存地址空间,因此空间复杂度为O(n)O(n)

算法 文章被收录于专栏

算法题的题解以及感受

全部评论
请问go的切片不是地址传递吗?为什么这里不用指针会错
点赞 回复 分享
发布于 2022-03-26 10:19

相关推荐

醒工硬件:1学校那里把xxxxx学院去了,加了学院看着就不像本校 2简历实习和项目稍微精简一下。字太多,面试官看着累 3第一个实习格式和第二个实习不一样。建议换行 4项目描述太详细了,你快把原理图贴上来了。比如可以这样描述:使用yyyy芯片,使用xx拓扑,使用pwm控制频率与占空比,进行了了mos/电感/变压器选型,实现了xx功能 建议把技术栈和你做的较为有亮点的工作归纳出来 5熟悉正反激这个是真的吗
点赞 评论 收藏
分享
26牛牛不会梦到感谢信:羡慕离职了还能吃吗现在就赶回去
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务