using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

    }

    public static IList<int> PreorderTraversal(TreeNode root) 

    {

        List<int> tree = new List<int>();

        if (root == null)

            return null;

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

​

        while (true)

        {

            if (root != null) 

            {

                stack.Push(root);

                root = root.left;

            }

            else 

            {

                if (stack.Count == 0)

                    break;

                root = stack.Pop();

                tree.Add(root.val);

                root = root.right;

            }

        }

        return tree;

    }

}

​

public class TreeNode 

{

    public int val;

    public TreeNode left;

    public TreeNode right;

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

}