VietMX Staff asked 3 years ago
Given a binary tree, return the preorder traversal of its nodes’ values. Can you do it without recursion?
Let’s use Stack:
- Set current node as
root - Check if current node is
nullthen return - Store current node value in the container
- Put
righton stack - Put
lefton stack - While stack is not empty
popfrom stack into current node. Note, theleftwill be on top of stack, and will be taken first- Repeat from step 2
Implementation
/**
* @param root: A Tree
* @return: Preorder in ArrayList which contains node values.
*/
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> rst = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
rst.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return rst;
}