Stack<TreeNode> s = new Stack<TreeNode>();
    
    public List<int> preorderTraversal (TreeNode root) {
        List<int> list = new List<int>();
        if(root == null)  //为空直接返回
        {
            return list;
        }
        TreeNode now = root;
        while(now != null || s.Count !=0)
        {
            if(now != null)
            {
                list.Add(now.val);
                s.Push(now);
                now = now.left;
            }
            else
            {
                now = s.Pop();
                now = now.right;
            }
        }
        return list;
    }

递推实现方式

用栈存储当前遍历到的结点,先往左边遍历,当遇到空时回到上一个结点,然后往右遍历,回到循环上面后继续一样的操作;如果右子树为空会返回更上一级和递归一样。