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

二叉树的前序遍历

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

方法一：python方法

解题思路

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

解题代码

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)$。