二叉树的中序遍历

[xszi]

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

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

[xszi]

递归写法：

const midorderTraversal = (root) => {
    let result = []
    const midorderTraverseNode = (node) => {
        if (node) {
            // 左子树
            midorderTraverseNode(node.left)
            // 跟节点
            result.push(node.value)
            // 右子树
            midorderTraverseNode(node.right)
        }
    }
    midorderTraverseNode(root)
    return result
}

迭代写法：

const midorderTraversal = (root) => {
    let result = []
    let stack = []
    let node = root
    while (stack.length || node) {
        // 先根节点入栈
        // 再左节点入栈
        // 所以左节点先出栈，根节点后出栈
        if (node) {
            stack.push(node)
            node = node.left
            continue
        }
        node = stack.pop()
        result.push(node.value)
        node = node.right
    }
    return result
}