每日leetcode-数组-144. 二叉树的前序遍历

分类：二叉树-二叉树的遍历

题目描述：

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

解题思路：

递归：

定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要首先将 root 节点的值加入答案，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(root:TreeNode):
            if not root:
                return []
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)
        res = list()
        preorder(root)
        return res

时间复杂度：O（n）其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O（n）为递归过程中栈的开销，平均情况下为 O(log n)O(logn)，最坏情况下树呈现链状，为 O(n)O(n)。

迭代：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res,stack = list(),list()
        stack.append(root) # 利用栈进行临时存储
        while len(stack):
            curr = stack.pop() # 取出一个节点，表示开始访问以该节点为根的子树
            res.append(curr.val) # 首先访问该节点（先序），之后顺序入栈右子树，左子树
            if curr.right:
                stack.append(curr.right)
            if curr.left:
                stack.append(curr.left)
        return res

时间复杂度O（n）

空间复杂度O（n）