class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode t = root;
        while(t!=null||!stack.isEmpty()){
            if(t!=null){
                res.add(t.val);
                stack.push(t);
                t = t.left;
            }
            else{
                t = stack.pop();
                t = t.right;
            }

        }
        return res;
    }
}