144_二叉树的前序遍历

类型：树

• 144. 二叉树的前序遍历 💛

  https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

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

  💡 递归

  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)，空间复杂度：O(n)

  💡 迭代

  class Solution:
      def preorderTraversal(self, root: TreeNode) -> List[int]:
          res = list()
          if not root:
              return res
  
          stack = []
          node = root
          while stack or node:
              while node:
                  res.append(node.val)
                  stack.append(node)
                  node = node.left
              node = stack.pop()
              node = node.right
          return res

  时间复杂度：O(n)，空间复杂度：O(n)