SOURCE

const root = {
  val: 1,
  left: {
    val: 2,
    left: null,
    right: { val: 4, left: null, right: null }
  },
  right: { val: 3, left: null, right: null }
};


/**
 * 二叉树中序遍历（递归实现）
 * 中序遍历顺序：左子树 → 当前节点 → 右子树
 * @param {TreeNode|null} root - 二叉树节点，节点结构 { val, left, right }
 * @returns {number[]} 中序遍历结果数组
 */
function treeOrderDeep(root) {
    if (!root) return []
    // 当前节点值
    const val = root.val
    // 递归遍历左子树，得到左子树序列
    const left = treeOrder(root.left)
    // 递归遍历右子树，得到右子树序列
    const right = treeOrder(root.right)
    // 拼接：左子树结果 + 当前节点 + 右子树结果
    return [...left, val, right]
}
/**
 * 迭代版 前序遍历 根→左→右
 * @param {TreeNode|null} root
 * @returns {number[]}
 */
function preTreeOrderIterator(root) {
    if (!root) return []
    const stack = [root]
    let res = []
    while(stack.length > 0) {
        const cur = stack.pop()
        res.push(cur.val)
        // 先压右节点，后压左节点，保证左先出栈
        cur.right && stack.push(cur.right)
        cur.left && stack.push(cur.left)
    }
    return res
}
console.log(preTreeOrderIterator(root))