容易想到的简单方法是使用递归；
另一种方式是借助于栈（Stack）先进后出的特点。
解一：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
解二：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
/**
* 借助栈先进后出的特点。前序遍历。
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()) { // begin of core code
TreeNode treeNode = stack.pop();
result.add(treeNode.val);
push(stack, treeNode.right);
push(stack, treeNode.left);
} // end of core code
return result;
}
/* 如果节点不为空则入栈 */
private void push(Stack<TreeNode> stack, TreeNode treeNode) {
if (treeNode != null) {
stack.push(treeNode);
}
}
}
温馨提示：
数据结构与算法通常有几个主要考察的点。你能get 到关键的点，并表述清楚，就过关了。
喜欢的话，别忘了点赞哟！
I am sunyoboy ! Welcome to @ sunyoboy@gmail.com
