Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
{1,#,2,3}
,1 \ 2 / 3
return
[1,2,3]
.
Note: Recursive solution is trivial, could you do it iteratively?
Solution 1: recursive DFS
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res=new ArrayList<>();
dfs(root,res);
return res;
}
private void dfs(TreeNode x, List<Integer> res) {
if (x==null) return;
res.add(x.val);
dfs(x.left, res);
dfs(x.right, res);
}
}
Solution 2: iterative DFS
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack=new LinkedList<>();
List<Integer> res=new ArrayList<>();
TreeNode x=root;
while (x!=null || !stack.isEmpty()) {
if (x!=null) {
res.add(x.val);
stack.push(x);
x=x.left;
}
else {
x=stack.pop();
x=x.right;
}
}
return res;
}
}
It is a best solution found that very popular and helpful:
回复删除https://www.youtube.com/watch?v=u2Py9rhxEuY&ab_channel=EricProgramming