import java.util.ArrayList;

import java.util.Deque;

import java.util.LinkedList;

import java.util.List;

public class Solution144 {

/**

* 前序遍历

*

* @param root 根节点

* @return 遍历数组

*/

public List<Integer> preorderTraversal(TreeNode root) {

if (root == null) {

return new ArrayList<>();

}

List<Integer> list = new ArrayList<>();

list.add(root.val);

list.addAll(preorderTraversal(root.left));

list.addAll(preorderTraversal(root.right));

return list;

}

/**

* 模拟栈

* @param root 根节点

* @return 数组

*/

public List<Integer> preorderTraversal2(TreeNode root) {

List<Integer> res = new ArrayList<>();

if (root == null) {

return res;

}

Deque<TreeNode> stack = new LinkedList<>();

TreeNode node = root;

while (!stack.isEmpty() || node != null) {

while (node != null) {

res.add(node.val);

stack.push(node);

node = node.left;

}

node = stack.pop();

node = node.right;

}

return res;

}

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;

}

}

}