Binary Tree Preorder Traversal 二叉树的前序遍历（3种方法)

Binary Tree Preorder Traversal 二叉树的前序遍历（3种方法)。二叉树的前序遍历。
给出一棵二叉树，返回其节点值的前序遍历。

样例
给出一棵二叉树 {1,#,2,3},

1
\
2
/
3
返回 [1,2,3].

挑战
你能使用非递归实现么？

3种方法：非递归、递归、分治

（1）Java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

//Version 1（Non-recursion）[Recommend]
public class Solution {
    /*
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    public List preorderTraversal(TreeNode root) {
        Stack stack = new Stack();
        List preorder = new ArrayList();

        if(root == null){
            return preorder;
        }
        stack.push(root);
        //根左右：最先进栈的root，最先出栈。然后，依次将右，左子节点 进栈，每次循环出栈（并存入preorder列表）的顺序满足先左后右。
        //即满足前序遍历：根左右
        while(!stack.empty()){
            TreeNode node = stack.pop();
            preorder.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
             if(node.left != null){
                stack.push(node.left);
            }
        }
        return preorder;
    }
}

 //Version2
 public class Solution{
     public ArrayList preorderTraversal(TreeNode root) {
         ArrayList result = new ArrayList();
         traverse(root, result);
         return result;

     }
      // 把root为跟的preorder加入result里面
     private void traverse(TreeNode root, ArrayList result){
         if(root == null){
             return;
         }
         result.add(root.val);
         traverse(root.left, result);
         traverse(root.right, result);
     }
 }


 //Version 3：Divide & Conquer
  public class Solution{
     public ArrayList preorderTraversal(TreeNode root) {
         ArrayList result = new ArrayList();
         //null or leaf
         if(root == null){
             return result;
         }
         //Divide
         ArrayList left = preorderTraversal(root.left);
         ArrayList right = preorderTraversal(root.right);

         //Conquer
         result.add(root.val);
         result.addAll(left);
         result.addAll(right);
         return result;
     }
 }

（2）C++

#include 
using namespace std;
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
    public:
    vector preorder;

    void traverse(TreeNode *root) {
        if (root == NULL) {
            return;
        }
        preorder.push_back(root->val);
        traverse(root->left);
        traverse(root->right);
    }

    vector preorderTraversal(TreeNode *root) {
        preorder.clear();
        traverse(root);
        return preorder;
    }
};