package com.app.main.LeetCode.tree;
import com.app.main.LeetCode.base.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
*
* 144
*
* medium
*
* https://leetcode.com/problems/binary-tree-preorder-traversal/
*
* Given a binary tree, return the preorder traversal of its nodes' values.
*
* Example:
*
* Input: [1,null,2,3]
* 1
* \
* 2
* /
* 3
*
* Output: [1,2,3]
* Follow up: Recursive solution is trivial, could you do it iteratively?
*
*
* Created with IDEA
* author:Dingsheng Huang
* Date:2019/10/31
* Time:下午2:49
*/
public class BinaryTreePreOrderTraversal {
// recursion
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
process(result, root);
return result;
}
private void process(List<Integer> result, TreeNode root) {
if (root != null) {
result.add(root.val);
if (root.left != null) {
process(result, root.left);
}
if (root.right != null) {
process(result, root.right);
}
}
}
// iterator
public List<Integer> preorderTraversal2(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
result.add(curr.val);
curr = curr.left;
}
curr = stack.pop();
curr = curr.right;
}
return result;
}
}
