Given the root of a binary tree, return the preorder traversal of its nodes' values.
Examples
Input: root = [1,null,2,3] Output: [1,2,3]
Input: root = [] Output: []
Input: root = [1] Output: [1]
Input: root = [1,2] Output: [1,2] Input: root = [1,null,2] Output: [1,2]
Constraints
The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Java Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> result = new LinkedList<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.add(p.val);
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}
}
