题目
结果
代码
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new LinkedList<>();
pot(ans, root);
return ans;
}
private void pot(List<Integer> ans, TreeNode root) {
if (root == null) {
return;
}
ans.add(root.val);
pot(ans, root.left);
pot(ans, root.right);
}
}
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new LinkedList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
ans.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return ans;
}
}
|
复杂度
时间复杂度：O（n）
空间复杂度：O（n）
两种算法做了同样的事情，迭代的算法是用栈模拟递归隐式产生的栈。