瞎写

入门级算法

题目在LeetCode上，主要记个思路以及通用的解法

144.二叉树前序遍历

94.二叉树中序遍历

145.二叉树后序遍历

• 只要理解了前中后序遍历的顺序，用DFS一把梭。前序：根->左->右；中序：左->根->右；后序：左->右->根；

1. 递归：

const parse = (root) => {
  if (!root) return [];
  const res = [];
  const dfs = (node) => {
    res.push(node.val);// 调整这个顺序即可
    dfs(node.left);
    dfs(node.right);
  };
  dfs(root);
  return res;
};

• 借助一个栈来进行节点的存储

2. 迭代：

const parse = (root) => {
  if (!root) return [];
  const res = [];
  const stack = [];
  while (root || stack.length) {
    // 前
    while (root) {
      stack.push(root);
      res.push(root.val); // 前序是一访问到节点就记录
      root = root.left;
    }
    root = stack.pop();
    root = root.right;
    // 中
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    res.push(root.val); // 中序是等遍历到左侧最后一个节点时再开始记录
    root = root.right;
    // 后
    while (root) {
      stack.push(root);
      res.unshift(root.val); // 后序是一访问到节点就反向记录
      root = root.right;
    }
    root = stack.pop();
    root = root.left;
  }
  return res;
};

3. 颜色标记

const parse = (root) => {
  if (!root) return [];
  const [WHITE, DARK] = [0, 1];
  let color, node;
  const res = [];
  const stack = [WHITE, root](/EricYangXD/LearnReact/wiki/WHITE,-root);
  while (stack.length) {
    [color, node] = stack.pop();
    if (!node) continue;
    // 当前指向的结点是未访问过的结点，将其右节点，根节点，左节点依次入栈(后入先出)
    // 前
    if (color === WHITE) {
      stack.push([WHITE, node.right]);
      stack.push([WHITE, node.left]);
      stack.push([DARK, node]);
    } else {
      res.push(node.val);
    }
    // 中
    if (color === WHITE) {
      stack.push([WHITE, node.right]);
      stack.push([DARK, node]);
      stack.push([WHITE, node.left]);
    } else {
      res.push(node.val);
    }
    // 后
    if (color === WHITE) {
      stack.push([DARK, node]);
      stack.push([WHITE, node.right]);
      stack.push([WHITE, node.left]);
    } else {
      res.push(node.val);
    }
  }
  return res;
};

4. Morris算法

// 中序
var inorderTraversal = function (root) {
  if (!root) return [];
  const res = [];
  let predecessor = null;
  while (root) {
    if (root.left) {
      predecessor = root.left;
      while (predecessor.right && predecessor.right !== root) {
        predecessor = predecessor.right;
      }
      if (!predecessor.right) {
        predecessor.right = root;
        root = root.left;
      } else {
        res.push(root.val);
        predecessor.right = null;
        root = root.right;
      }
    } else {
      res.push(root.val);
      root = root.right;
    }
  }
  return res;
};

102.二叉树层序遍历

var levelOrder = function (root) {
    if (!root) return [];
    const res = [];
    const queue = [root];

    while (queue.length) {
        const levelSize = queue.length;// 表示当前这一层的节点数
        res.push([]);// 先把当前层的数组写入，然后利用res.length-1往里写数据
        for (let i = 0; i < levelSize; i++) {// 把当前层的所有节点都遍历一遍
            const node = queue.shift();
            res[res.length - 1].push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    return res;
};