Traversal

Binary Tree Preorder Traversal

• Time: O(N)
• Space: O(1)

// Binary Tree Preorder Traversal Recursive
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    preorderTraversal(root, ret);
    return ret;
}

private void preorderTraversal(TreeNode node, List<Integer> list) {
    if (node == null) {
        return;
    }
    list.add(node.val);
    preorderTraversal(node.left, list);
    preorderTraversal(node.right, list);
}

// Binary Tree Preorder Traversal Iterate
public List<Integer> preorderTraversal_2(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    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;
}

// Binary Tree Inorder Traversal Recursive
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    inorderTraversal(root, ret);
    return ret;
}
public void inorderTraversal(TreeNode node, List<Integer> list) {
    if (node == null) {
        return;
    }
    inorderTraversal(node.left, list);
    list.add(node.val);
    inorderTraversal(node.right, list);
}

// Binary Tree Inorder Traversal Iterate
public List<Integer> inorderTraversal_2(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while (!stack.isEmpty() || p != null) {
        if (p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            result.add(node.val);
            p = node.right;
        }
    }
    return result;
}

// Binary Tree Postorder Traversal Recursive
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    postorderTraversal(root, ret);
    return ret;
}
public void postorderTraversal(TreeNode node, List<Integer> list) {
    if (node == null) {
        return;
    }
    postorderTraversal(node.left, list);
    postorderTraversal(node.right, list);
    list.add(node.val);
}

// Binary Tree Postorder Traversal Iterate
public List<Integer> postorderTraversal_2(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode p = root;
    while (!stack.isEmpty() || p != null) {
        if (p != null) {
            stack.push(p);
            result.addFirst(p.val);
            p = p.right;
        } else {
            TreeNode node = stack.pop();
            p = node.left;
        }
    }
    return result;
}