二叉树的中序遍历

[Cosen95]

leetcode: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

[Cosen95]

递归

第一种，我们可以通过递归来实现。这种方法代码比较简洁，语意性也比较强：

/**
 * 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) {
    if (root) {
        return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
    } else {
        return []
    }
};

颜色标记法

第二种是通过使用颜色标记法实现, 思路如下:

• 维护一个栈
• 将已访问过的元素标记为灰色, 未访问过的元素标记为白色
• 从栈顶取出访问元素:
  • 若为灰色元素, 则push进结果数组中
  • 若为白色元素, 按照右 -> 中 -> 左的顺序推入栈, 同时将白色元素标记为灰色元素

/**
 * 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) {
    let res = [];
    if (!root) return res
    let stack = [];
    stack.push({
        color: 'white',
        node: root
    })
    while (stack.length) {
        const { color, node } = stack.pop();
        if (color === 'grey') {
            res.push(node.val)
        } else {
            node.right && stack.push({ color: 'white', node: node.right })
            stack.push({ color: 'grey', node })
            node.left && stack.push({ color: 'white', node: node.left})
        }
    }
    return res
};