144. Binary Tree Preorder Traversal
题目描述
Given a binary tree, return the preorder traversal of its nodes’ values.
方法思路
Approach1: 递归 recursive
class Solution {
//Runtime: 0 ms, faster than 100.00%
//Memory Usage: 36.3 MB, less than 14.66%
List<Integer> res = new LinkedList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return res;
res.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return res;
}
}
Approach2: iteratively
class Solution{
//Runtime: 0 ms, faster than 100.00%
//Memory Usage: 36.3 MB, less than 11.50%
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
res.add(node.val);
if(node.right != null)
stack.push(node.right);
if(node.left != null)
stack.push(node.left);
}
return res;
}
}