/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

   public static List<Integer> resultlist = new ArrayList<Integer>();

    public static void dfs (TreeNode root ,boolean flag ) {

        if(flag==true)

        {

            resultlist.clear();

        }

        if(root==null)

        {

            return ;

        }

            resultlist.add(root.val);

        if(root.left!=null)

        {

            dfs(root.left,false);

        }

        if(root.right!=null)

        {

            dfs(root.right,false);

        }

    }

    public static List<Integer> preorderTraversal(TreeNode root ) {

        dfs(root,true);

        return resultlist;

    }

}

 public static List<Integer> preorderTraversal(TreeNode root ) {

        List<Integer> result = new ArrayList<>();

        if(root == null)

            return result;

        Stack<TreeNode> stack = new Stack<TreeNode>();

        stack.push(root);

        while(!stack.empty()){

            TreeNode n = stack.pop();

            result.add(n.val);

            if(n.right != null){

                stack.push(n.right);

            }

            if(n.left != null){

                stack.push(n.left);

            }

        }

        return result;

    }