144.preorderTraversal.py

# Given the root of a binary tree, return the preorder traversal of its nodes'
# values.
#
#
#  Example 1:
#
#
# Input: root = [1,null,2,3]
# Output: [1,2,3]
#
#
#  Example 2:
#
#
# Input: root = []
# Output: []
#
#
#  Example 3:
#
#
# Input: root = [1]
# Output: [1]
#
#
#
#  Constraints:
#
#
#  The number of nodes in the tree is in the range [0, 100].
#  -100 <= Node.val <= 100
#
#
#
#  Follow up: Recursive solution is trivial, could you do it iteratively?
#
#  Related Topics Stack Tree Depth-First Search Binary Tree 👍 7669 👎 196
from typing import Optional, List


# leetcode submit region begin(Prohibit modification and deletion)
# 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: Optional[TreeNode]) -> List[int]:
        # base case
        if not root:
            return []
        # L N R
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

# leetcode submit region end(Prohibit modification and deletion)

if __name__ == "__main__":
    s = Solution()
    root = TreeNode(
        1, TreeNode(2), TreeNode(3)
    )
    assert s.preorderTraversal(root) == [1,2,3]
    # Output: [1,2,3]