<jupyter_start><jupyter_text>Given a binary tree, return the preorder traversal of its nodes' values.Example:    Input: [1,null,2,3]       1        \         2        /       3    Output: [1,2,3]<jupyter_code># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        '''
        :param root: TreeNode
        :return: List[int]
        '''
        # order: root, left, right
        # recursive solution
        res = []
        if root:
            res.append(root.val)
            res += self.preorderTraversal(root.left)
            res += self.preorderTraversal(root.right)
        return res
            
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        '''
        :param root: TreeNode
        :return: List[int]
        '''
        # order: root, left, right
        # iterative solution
        # add root val in res first, then stack pop the left node val, finally right ones
        # finally, the stack contains root, left and right subtree val

        res, stack = [], [root]
        while stack:
            node = stack.pop()
            
            if node:
                res.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
                
        return res<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10181818181818182, 'fraction_numerical': 0.005454545454545455, 'mean_word_length': 1.6586151368760065, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '126081', 'license': 'MIT', 'n_tokens_mistral': 481, 'n_tokens_neox': 469, 'n_words': 139, 'path': 'DSA/tree/PreorderTraversal.ipynb', 'repo_name': 'lance-lh/Data-Structures-and-Algorithms', 'size': '1650'}