//前序遍历递归
    public List<Integer> preorderTraversal_1(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        if(root == null)
            return ans;
        subPreorderTraversal(root, ans);
        return ans;
    }
    private void subPreorderTraversal(TreeNode root, List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        subPreorderTraversal(root.left, list);
        subPreorderTraversal(root.right, list);
    }


    //前序遍历非递归，放入栈的顺序是：初始化是root，然后按照右、左的顺序放入
    public List<Integer> preorderTraversal_2(TreeNode root) {
        LinkedList<Integer> ans = new LinkedList<>();
        if(root == null)
            return ans;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.empty()){
            TreeNode tmp = stack.pop();
            ans.add(tmp.val);
            if(tmp.right != null)
                stack.push(tmp.right);
            if(tmp.left != null)
                stack.push(tmp.left);
        }
        return ans;
    }