题目
给定一个二叉树，返回它的 前序 遍历。
思路一 递归
class Solution {
public List
<Integer> preorderTraversal(TreeNode root
) {
List
<Integer> list
= new ArrayList<>();
helper(root
, list
);
return list
;
}
public void helper(TreeNode root
, List
<Integer> list
) {
if (root
!= null
) {
list
.add(root
.val
);
if (root
.left
!= null
) {
helper(root
.left
, list
);
}
if (root
.right
!= null
) {
helper(root
.right
,list
);
}
}
}
}
思路二 迭代
class Solution {
public List
<Integer> preorderTraversal(TreeNode root
) {
List
<Integer> list
= new ArrayList<>();
Stack
<TreeNode> stack
= new Stack<>();
while (!stack
.isEmpty() || root
!= null
) {
if (root
!= null
) {
list
.add(root
.val
);
stack
.push(root
);
root
= root
.left
;
} else {
root
= stack
.pop();
root
= root
.right
;
}
}
return list
;
}
}
复杂度分析
时间复杂度：访问每个节点恰好一次，时间复杂度为 O(N)，其中 N 是节点的个数，也就是树的大小。 空间复杂度：取决于树的结构，最坏情况存储整棵树，因此空间复杂度是 O(N)。
