94.Binary Tree Inorder Traversal

1-DFS On

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void dfs(List<Integer> ans, TreeNode root){
        if(root == null){
            return;
        }
        dfs(ans, root.left);
        ans.add(root.val);
        dfs(ans, root.right);
        return;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(ans, root);
        return ans;
    }
}

2-Using Stack

https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31213/

On

Here’s my iterative solution.

I use pushAllLeft() to push all the left children of one Node into the stack, so that my idea looks clear:

We push all the left children of root into the stack until there’s no more nodes.
Then we pop from the stack which we’d call cur.
Add cur to result list
Recursively call pushAllLeft() on cur's right child.

public List<Integer> inorderTraversal2(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;

    Stack<TreeNode> stack = new Stack<>();
    pushAllLeft(root, stack);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        res.add(cur.val);
        pushAllLeft(cur.right, stack);
    }
    return res;
}

public void pushAllLeft(TreeNode node, Stack stack){
    while (node != null) {
        stack.add(node);
        node = node.left;
    }
}


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root == null)
            return ans;

        Deque<TreeNode> stack = new ArrayDeque<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            ans.add(root.val);
            root = root.right;   
        }
        return ans;
    }
}