Given a binary tree, return thepreordertraversal of its nodes' values.

For example:
Given binary tree{1,#,2,3},

   1
    \
     2
    /
   3

return[1,2,3].

Answer: https://leetcode.com/problems/binary-tree-preorder-traversal/description/

前序遍历（PreOrder): 根左右 中序遍历（InOrder）: 左根右 后续遍历（PostOrder）: 左右根

遍历法： 递归的函数（Traversal function） is void -- 无返回类型， result 作为参数传入递归方法，可看作全局变量

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        IList<int> result = new List<int>();

        Traversal(root,result);
        return result;
    }

    public void Traversal(TreeNode root, IList<int> result){
        if (root == null){
            return;
        }
        result.Add(root.val);
        Traversal(root.left,result);
        Traversal(root.right,result);
    }
}

分治法 divide conquer： 函数有返回类型， 函数可直接自己调自己(不用传result 作为参数)

public class Solution {
    public IList<int> PreorderTraversal(TreeNode root) {
        List<int> result = new List<int>();

       if (root == null){
            return result;
        }

        IList<int> leftTreeList = PreorderTraversal(root.left);
        IList<int> rightTreeList = PreorderTraversal(root.right);

        result.Add(root.val);        
        result.AddRange(leftTreeList);
        result.AddRange(rightTreeList);
        return result;
    }

}