递归法
递归法比较简单，使用好递归三部曲
1.确定递归方法的输入输出参数
2.确定递归的终止条件
3.确定递归的单层逻辑
顺便熟悉了下树节点的定义，成员变量不指定访问权限，就是包内可见。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root, res);
return res;
}
private void dfs(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
dfs(root.left, res);
dfs(root.right, res);
}
}
迭代法
果然一看就会，一写就废，还是要多写一下的，迭代，前序遍历应该是最简单的了，从栈里取出后，再将左右子树压到栈中，不过先右后左，因为出栈是反的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> s = new Stack<>();
s.push(root);
while(!s.empty()) {
root = s.pop();
res.add(root.val);
if (root.right != null) {
s.push(root.right);
}
if (root.left != null) {
s.push(root.left);
}
}
return res;
}
}
