树的遍历(Traversal)

深度和广度优先搜索

• 深度优先搜索（Depth-First Search, DFS）：沿着树的某一分支深入到底，访问这个分支的所有节点后，再回溯到上一层次，继续探索其他分支，一直进行到所有节点都被访问为止。
• 广度优先搜索（Breadth-First Search, BFS）：从起始节点开始，先访问其所有直接相邻的节点，然后对每个相邻节点再访问他们的未被访问过的相邻节点，从树根开始一层一层地访问树的节点。

深度优先搜索又分为前序遍历、中序遍历和后序遍历，广度优先搜索就是层次遍历。

树节点的定义

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 */

二叉树的前序遍历(根左右)

LC：144.二叉树的前序遍历 (opens new window)

// 递归 O(n) O(n)
const preorderTraversal = function (root) {
  const ans = [];
  const dfs = (node) => {
    if (node === null) return;
    ans.push(node.val);
    dfs(node.left);
    dfs(node.right);
  };
  dfs(root);
  return ans;
};

// 不使用辅助函数
const preorderTraversal = function (root) {
  if (root === null) return [];
  return [root.val].concat(preorderTraversal(root.left)).concat(preorderTraversal(root.right));
};

// 迭代 O(n) O(n)
const preorderTraversal = function (root) {
  const ans = [];
  if (root === null) return [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    ans.push(node.val);
    node.right && stack.push(node.right);
    node.left && stack.push(node.left);
  }
  return ans;
};

// Morris O(n) O(1)
const preorderTraversal = function (root) {
  const ans = [];
  if (root === null) return ans;
  let p1 = root;
  let p2 = null;
  while (p1) {
    p2 = p1.left;
    if (p2) {
      while (p2.right && p2.right !== p1) {
        p2 = p2.right;
      }
      if (p2.right === null) {
        ans.push(p1.val);
        p2.right = p1;
        p1 = p1.left;
        continue;
      } else {
        p2.right = null;
      }
    } else {
      ans.push(p1.val);
    }
    p1 = p1.right;
  }
  return ans;
};

二叉树的中序遍历(左根右)

LC：144.二叉树的中序遍历 (opens new window)

// 递归 O(n) O(n)
const inorderTraversal = function (root) {
  const ans = [];
  const dfs = (node) => {
    if (node === null) return;
    dfs(node.left);
    ans.push(node.val);
    dfs(node.right);
  };
  dfs(root);
  return ans;
};

// 不使用辅助函数
const inorderTraversal = function (root) {
  if (root === null) return [];
  return inorderTraversal(root.left).concat(root.val, inorderTraversal(root.right));
};

// 迭代 O(n) O(n)
const inorderTraversal = function (root) {
  const ans = [];
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) {
      // 正向放入当前节点的所有左节点
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop(); // 取出最后放入的左节点，再存入结果
    ans.push(cur.val);
    cur = cur.right;
  }
  return ans;
};

// Morris O(n) O(1)
const inorderTraversal = function (root) {
  const ans = [];
  let predecessor = null;
  while (root) {
    if (root.left) {
      // predecessor节点就是当前root节点向左走一步，然后一直向右走至无法走为止
      predecessor = root.left;
      while (predecessor.right && predecessor.right !== root) {
        predecessor = predecessor.right;
      }
      if (!predecessor.right) {
        // 让predecessor的右指针指向root，继续遍历左子树
        predecessor.right = root;
        root = root.left;
      } else {
        // 说明左子树已经访问完了，我们需要断开链接
        ans.push(root.val);
        predecessor.right = null;
        root = root.right;
      }
    } else {
      // 如果没有左孩子，则直接访问右孩子
      ans.push(root.val);
      root = root.right;
    }
  }
  return ans;
};

二叉树的后序遍历(左右根)

LC：144.二叉树的后序遍历 (opens new window)

// 递归 O(n) O(n)
const postorderTraversal = function (root) {
  const ans = [];
  const dfs = (node) => {
    if (node === null) return;
    dfs(node.left);
    dfs(node.right);
    ans.push(node.val);
  };
  dfs(root);
  return ans;
};

// 不使用辅助函数
const postorderTraversal = function (root) {
  if (root === null) return [];
  return postorderTraversal(root.left).concat(postorderTraversal(root.right), root.val);
};

// 迭代 O(n) O(n)
const postorderTraversal = function (root) {
  if (root === null) return [];
  const ans = [];
  const stack = [];
  let prevRight = null;
  let cur = root;
  while (cur || stack.length) {
    while (cur) { // 一直找到最左边的左叶子节点
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop(); // 取出栈顶
    if (cur.right === null || cur.right === prevRight) {
      // 没有右子树或者右子树在上次被遍历过
      ans.push(cur.val);
      prevRight = cur;
      cur = null;
    } else {
      // 有右子树，则把当前根节点移到右节点上
      stack.push(cur);
      cur = cur.right;
    }
  }
  return ans;
};

// Morris O(n) O(1)
const addPath = function (ans, node) {
  const tmp = [];
  while (node != null) {
    tmp.push(node.val);
    node = node.right;
  }
  for (let i = tmp.length - 1; i >= 0; --i) {
    ans.push(tmp[i]);
  }
};
const postorderTraversal = function (root) {
  if (root == null) return [];
  const ans = [];
  let p1 = root;
  let p2 = null;
  while (p1) {
    p2 = p1.left;
    if (p2) {
      while (p2.right && p2.right !== p1) {
        p2 = p2.right;
      }
      if (p2.right === null) {
        p2.right = p1;
        p1 = p1.left;
        continue;
      } else {
        p2.right = null;
        addPath(ans, p1.left);
      }
    }
    p1 = p1.right;
  }
  addPath(ans, root);
  return ans;
};

二叉树的层次遍历

const levelOrderTraversal = function (root) {
  if (root === null) return [];
  const ans = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    ans.push(node.val);
    if (node.left) {
      queue.push(node.left);
    }
    if (node.right) {
      queue.push(node.right);
    }
  }
  return ans;
};