94 Binary Tree Inorder Traversal

https://leetcode.com/problems/binary-tree-inorder-traversal/#/description

Given a binary tree, return theinordertraversal of its nodes' values.

For example:
Given binary tree[1,null,2,3],

   1
    \
     2
    /
   3

return[1,3,2].

Note:Recursive solution is trivial, could you do it iteratively?

分析及代码

recursively

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    traversal(res, root);
    return res;
}

private void traversal(List<Integer> res, TreeNode root) {
    if(root == null) {
        return;
    }
    traversal(res, root.left);
    res.add(root.val);
    traversal(res, root.right);
}

iteratively

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()) {
        while(cur != null) {
            stack.offerLast(cur);
            cur = cur.left;
        }
        cur = stack.pollLast();
        res.add(cur.val);
        cur = cur.right;
    }
    return res;
}

bug free. 虽然是基础题，但是一遍过还是挺开心的