Given the root of a binary tree, return the preorder traversal of its nodes' values.

&nbsp;
Example 1:

Input: root = [1,null,2,3]
Output: [1,2,3]


Example 2:

Input: root = []
Output: []


Example 3:

Input: root = [1]
Output: [1]


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [0, 100].
	-100 &lt;= Node.val &lt;= 100


&nbsp;
Follow up: Recursive solution is trivial, could you do it iteratively?

from collections import deque
from typing import List, Optional

class Solution:
    """
    Time: O(n)
    """

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []

        queue = deque([root])
        preorder = []

        while queue:
            node = queue.pop()
            preorder.append(node.val)

            if node.right is not None:
                queue.append(node.right)
            if node.left is not None:
                queue.append(node.left)

        return preorder

class Solution:
    """
    Time: O(n)
    """

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return list(self.preorder_generator(root))

    @classmethod
    def preorder_generator(cls, tree: Optional[TreeNode]):
        if tree is not None:
            yield tree.val
            yield from cls.preorder_generator(tree.left)
            yield from cls.preorder_generator(tree.right)
class Solution {
     public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderTraversal2(root, result);
        return result;
    }


    public List<Integer> preorderTraversal2(TreeNode root,List<Integer> result) {
        if(root!=null){
               result.add(root.val);
            if(root.left!=null){
                preorderTraversal2(root.left,result);
            }
            if(root.right!=null){
                preorderTraversal2(root.right,result);
            }
        }
        return result;
    }
}
class Solution {
    void solve(TreeNode *root, vector<int> &ans){
        if(root == NULL) return;
        ans.push_back(root->val);
        solve(root->left, ans);
        solve(root->right, ans);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        solve(root, ans);
        return ans;
    }
};
var preorderTraversal = function(root) {
    let res = []
    
    const check = node => {
        if(node === null) return
        else res.push(node.val)
        
        if(node.left !== null) check(node.left)
        if(node.right !== null) check(node.right)
    }
    
    check(root)
    
    return res
};
Binary Tree Preorder Traversal