public List<Integer> preorderTraversal(TreeNode root) {

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

         list = dfs(root, list);

         return list;

     }

     public static List<Integer> dfs(TreeNode root, List<Integer> list) {

         if(root == null) {

             return list;

         }

         else {

             list.add(root.val);

             list = dfs(root.left, list);

             list = dfs(root.right, list);

             return list;

         }

     }

     public List<Integer> preorderTraversal(TreeNode root) {

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

         TreeNode tmp = root;

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

         while(tmp != null || !stack.isEmpty()) {

             //将所有左孩子压栈，直到没有左孩子，并且由于是先序遍历，所以在压左孩子的时候就放入结果list中

             while(tmp != null) {

                 list.add(tmp.val);

                 stack.push(tmp);

                 tmp = tmp.left;

             }

             //如果左孩子压完了，就访问右孩子

             if(!stack.isEmpty()) {

                 tmp = stack.pop();

                 tmp = tmp.right;

             }

         }

         return list;

     }

     public List<Integer> inorderTraversal(TreeNode root) {

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

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

         TreeNode tmp = root;

         while(tmp != null || !stack.isEmpty()) {

             while(tmp != null) {

                 stack.push(tmp);

                 tmp = tmp.left;

             }

             //与先序不同的是，在弹出时放入结果list

             if(!stack.isEmpty()) {

                 tmp = stack.pop();

                 list.add(tmp.val);

                 tmp = tmp.right;

             }

         }

         return list;

     }