二叉树的中序遍历

[ChuChencheng]

问题

LeetCode 94

如标题

解

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const result = []

    const traverse = (node, list) => {
        if (!node) return
        if (node.left) traverse(node.left, list)
        list.push(node.val)
        if (node.right) traverse(node.right, list)
    }

    traverse(root, result)

    return result
};

非递归1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const result = []
    if (!root) return result
    const stack = []

    // 先将左子节点都入栈
    let node = root
    while (node) {
        stack.push(node)
        node = node.left
    }
    while (stack.length) {
        const node = stack.pop()
        result.push(node.val)
        // 针对每个出栈的节点，对其右子节点再执行一次左子节点入栈
        if (node.right) {
            let rightNode = node.right
            while (rightNode) {
                stack.push(rightNode)
                rightNode = rightNode.left
            }
        }
    }

    return result
};

非递归2

上述版本中执行了两个步骤：

1. 从根节点开始，循环将左子节点入栈
2. 针对出栈的节点执行步骤1

从代码中可以看到，有两部分代码是类似的：

while (node) {
    stack.push(node)
    node = node.left
}

可以将相同的部分合并起来：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const result = []
    if (!root) return result
    const stack = []

    let node = root
    while (node || stack.length) {
        while (node) {
            stack.push(node)
            node = node.left
        }
        const last = stack.pop()
        result.push(last.val)
        node = last.right
    }

    return result
};