二叉树前序遍历（递归及非递归）

非递归

需要利用栈

一开始将root入栈；

循环结束条件：栈空；

每次循环，先使栈顶元素出栈，将其数值加入list中，再将其右结点入栈，左结点入栈，因为前序遍历是先根再左后右，入栈顺序要先右后左；

import java.util.ArrayList;
import java.util.Stack;
/*** Definition for binary tree* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {public ArrayList<Integer> preorderTraversal(TreeNode root) {ArrayList<Integer> a = new ArrayList<Integer>();Stack<TreeNode> stack = new Stack<TreeNode>();if (root == null){return a;}stack.push(root);while(!stack.isEmpty()){TreeNode node = stack.pop();a.add(node.val);if(node.right != null){stack.push(node.right);}if(node.left != null){stack.push(node.left);}   }return a;}
}

递归 

import java.util.ArrayList;
import java.util.Stack;
/*** Definition for binary tree* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {public ArrayList<Integer> preorderTraversal(TreeNode root) {ArrayList<Integer> a = new ArrayList<Integer>();if (root == null){return a;}a.add(root.val);if(root.left != null){a.addAll(preorderTraversal(root.left));}if(root.right != null){a.addAll(preorderTraversal(root.right));}return a;}
}