leetcode-0094 二叉树的中序遍历

[GuoLizhi]

题目地址 https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

1.递归

时间复杂度O(n) 空间复杂度O(n)

var inorderTraversal = function(root) {
  const result = []
  if (root === null) {
    return result
  }
  _inorderTraversal(root, result)
  return result
};
var _inorderTraversal = function (node, result) {
  if (node === null) {
    return
  }
  _inorderTraversal(node.left, result)
  result.push(node.val)
  _inorderTraversal(node.right, result)
}

2.迭代

时间复杂度O(n) 空间复杂度O(n)

var inorderTraversal = function(root) {
  const result = []
  const stack = []
  if (root === null) {
    return result
  }
  let curr = root
  while (curr != null || stack.length) {
    // 先将所有的左儿子入栈，这个是中序遍历的重点所在！！！
    while (curr !== null) {
      stack.push(curr)
      curr = curr.left
    }
    // 取出一个元素
    const node = stack.pop()
    result.push(node.val)
    // 如果这个节点还有右儿子
    curr = node.right
  }
  return result
}

3. 颜色标记法

/**
 * 前序遍历：自身->左孩子->右孩子
 * 中序遍历：左孩子->自身->右孩子
 * 后序遍历：右孩子->自身->左孩子
 * 因此对于中序遍历而言，左孩子需要放置在栈顶，所以是最后入栈
 * 
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const WHITE = 0; // 白色节点表示没有访问过
    const GRAY = 1; // 灰色节点表示访问过了
    const stack = [[root, WHITE]];
    const result = [];
    while (stack.length > 0) {
        const [node, color] = stack.pop();
        if (node === null) continue;
        if (color === WHITE) {
            stack.push([node.right, WHITE]);
            stack.push([node, GRAY]);
            stack.push([node.left, WHITE]);
        } else {
            result.push(node.val);
        }
    }
    return result;
};