0094. Binary Tree Inorder Traversal.md

Recursion

/*
As long as there is root or stack has length, we loop over. In the loop, if there is a root, we push root into stack and go see the left, until there is no root on left subtree, then we find the nearest last root, and put it into stack, then loop the right subtree.
*/
var inorderTraversal = function(root, res = []) {
    if(!root) return [];
    if(root.left) root.left = inorderTraversal(root.left, res);
    res.push(root.val);
    if(root.right) root.right = inorderTraversal(root.right, res);
    return res;
}

Iteration

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */

var inorderTraversal = function(root) {
    let stack = [];
    let res = [];
    while(root || stack.length) {
        if(root) {
            stack.push(root);
            root = root.left;
        } else {
            root = stack.pop();
            res.push(root.val);
            root = root.right;
        }
    }
    return res;
}