94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

/**
 * 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 res = []
    // const traver = (root) => {
    //     if (!root) { return res };
    //     traver(root.left);
    //     res.push(root.val)
    //     traver(root.right)
    //     return res
    // }
    // return traver(root)
    // 迭代法===========================
    // 入栈 左 -> 右
    // 出栈 左 -> 中 -> 右
    // let stack = [], res = [];
    // let cur = root;
    // while (stack.length || cur) {
    //     if (cur) {
    //         stack.push(cur);
    //         // 左
    //         cur = cur.left;
    //     } else {
    //         // --> 弹出 中
    //         cur = stack.pop();
    //         res.push(cur.val);
    //         cur = cur.right
    //     }
    // }
    // return res
    // 终极版==============================
    const stack = [], res = [];
    if (root) { stack.push(root) }
    while (stack.length) {
        const node = stack.pop();
        if (!node) {
            res.push(stack.pop().val);
            continue;
        }
        if (node.right) stack.push(node.right);
        stack.push(node);
        // 占位标识符
        stack.push(null);
        if (node.left) stack.push(node.left);
    }
    return res;
};