Skip to main content

二叉树相关题目

有以下三个命题方向需要大家重点掌握：

  • 迭代法实现二叉树的先、中、后序遍历
  • 二叉树层序遍历的衍生问题
  • 翻转二叉树

“遍历三兄弟”的迭代实现

从先序遍历说起

给定一个二叉树，返回它的前序（先序）遍历序列。

示例:

输入: [1,null,2,3]

1
 \
  2
 /
3
输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归

function preOrderTrans(root) {
  const result = [];
  function dfs(root) {
    if (root) {
      result.push(root.val);
      if (root.left) dfs(root.left);
      if (root.right) dfs(root.right);
    }
  }
  dfs(root);
  return result;
}

非递归

合理地安排入栈和出栈的时机、使栈的出栈序列符合二叉树的前序遍历规则。

前序遍历的规则是，先遍历根结点、然后遍历左孩子、最后遍历右孩子——这正是我们所期望的出栈序列。按道理，入栈序列和出栈序列相反，我们似乎应该按照 右->左->根 这样的顺序将结点入栈。不过需要注意的是，我们遍历的起点就是根结点，难道我们要假装没看到这个根结点、一鼓作气找到最右侧结点之后才开始进行入栈操作吗？答案当然是否定的，我们的出入栈顺序应该是这样的：

  • 将根结点入栈
  • 取出栈顶结点，将结点值 push 进结果数组
  • 若栈顶结点有右孩子，则将右孩子入栈
  • 若栈顶结点有左孩子，则将左孩子入栈

这整个过程，本质上是将当前子树的根结点入栈、出栈，随后再将其对应左右子树入栈、出栈的过程。

重复 2、3、4 步骤，直至栈空，我们就能得到一个先序遍历序列。

function preOrderTrans(root) {
  const result = [];
  const stack = [];
  if (root) {
    stack.push(root);
    while (stack.length) {
      const node = stack.pop();
      result.push(node.val);
      if (node.right) stack.push(node.right);
      if (node.left) stack.push(node.left);
    }
  }
  return result;
}

异曲同工的后序遍历迭代实现

递归

// 左右根
function postOrderTrans(root) {
  const result = [];
  function dfs(root) {
    if (root) {
      if (root.left) dfs(root.left);
      if (root.right) dfs(root.right);
      result.push(root.val);
    }
  }
  dfs(root);
  return result;
}

非递归

后序遍历的出栈序列，按照规则应该是 左 -> 右 -> 根 。这个顺序相对于先序遍历，最明显的变化就是根结点的位置从第一个变成了倒数第一个。

如何做到这一点呢？与其从 stack 这个栈结构上入手，不如从 res 结果数组上入手!

function postOrderTrans(root) {
  // 根左右 - 先序 - 入栈 先右后左 ==== 后序遍历等价于先序遍历先入栈右子节点再入栈左子节点，之后的出栈结果（根右左）再反转（左右根）
  const result = [];
  const stack = [];
  if (root) {
    stack.push(root);
    while (stack.length) {
      const node = stack.pop();
      if (node.left) stack.push(node.left);
      if (node.right) stack.push(node.right);
      result.push(node.val);
    }
  }
  return result.reverse();
}

思路清奇的中序遍历迭代实现

递归

function inOrderTrans(root) {
  const result = [];
  function dfs(root) {
    if (root) {
      if (root.left) dfs(root.left);
      result.push(root.val);
      if (root.right) dfs(root.right);
    }
  }
  dfs(root);
  return result;
}

非递归

先序遍历和后序遍历之所以可以用同一套代码框架来实现，本质上是因为两者的出栈、入栈逻辑差别不大——都是先处理根结点，然后处理孩子结点。而中序遍历中，根结点不再出现在遍历序列的边界、而是出现在遍历序列的中间。这就意味着无论如何我们不能再将根结点作为第一个被 pop 出来的元素来处理了——出栈的时机被改变了，这意味着入栈的逻辑也需要调整。这一次我们不能再通过对 res 动手脚来解决问题，而是需要和 stack 面对面 battle。

中序遍历的序列规则是 左 -> 中 -> 右 ，这意味着我们必须首先定位到最左的叶子结点。在这个定位的过程中，必然会途径目标结点的父结点、爷爷结点和各种辈分的祖宗结点：

const inorderTraversal = function(root) {
  // 定义结果数组
  const res = [];
  // 初始化栈结构
  const stack = [];
  // 用一个 cur 结点充当游标
  let cur = root;
  // 当 cur 不为空、或者 stack 不为空时，重复以下逻辑
  while (cur || stack.length) {
    // 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来
    while (cur) {
      // 将途径的结点入栈
      stack.push(cur);
      // 继续搜索当前结点的左孩子
      cur = cur.left;
    }
    // 取出栈顶元素
    cur = stack.pop();
    // 将栈顶元素入栈
    res.push(cur.val);
    // 尝试读取 cur 结点的右孩子
    cur = cur.right;
  }
  // 返回结果数组
  return res;
};
编码复盘

  1. 两个 while ：内层的 while 的作用是在寻找最左叶子结点的过程中，把途径的所有结点都记录到 stack 里。记录工作完成后，才会走到外层 while 的剩余逻辑里——这部分逻辑的作用是从最左的叶子结点开始，一层层回溯遍历左孩子的父结点和右侧兄弟结点，进而完成整个中序遍历任务。

  2. 外层 while 的两个条件： cur 的存在性和 stack.length 的存在性，各自是为了限制什么？

    1. stack.length 的存在性比较好理解， stack 中存储的是没有被推入结果数组 res 的待遍历元素。只要 stack 不为空，就意味着遍历没有结束， 遍历动作需要继续重复。

    2. cur 的存在性就比较有趣了。它对应以下几种情况：

      1. 初始态， cur 指向 root 结点，只要 root 不为空， cur 就不为空。此时判断了 cur 存在后，就会开始最左叶子结点的寻找之旅。这趟“一路向左”的旅途中， cur 始终指向当前遍历到的左孩子。

      2. 第一波内层 while 循环结束， cur 开始承担中序遍历的遍历游标职责。 cur 始终会指向当前栈的栈顶元素，也就是“一路向左”过程中途径的某个左孩子，然后将这个左孩子作为中序遍历的第一个结果元素纳入结果数组。假如这个左孩子是一个叶子结点，那么尝试取其右孩子时就只能取到 null ，这个 null 的存在，会导致内层循环 while 被跳过，接着就直接回溯到了这个左孩子的父结点，符合 左->根 的序列规则

      3. 假如当前取到的栈顶元素不是叶子结点，同时有一个右孩子，那么尝试取其右孩子时就会取到一个存在的结点。 cur 存在，于是进入内层 while 循环，重复“一路向左”的操作，去寻找这个右孩子对应的子树里最靠左的结点，然后去重复刚刚这个或回溯、或“一路向左”的过程。如果这个右孩子对应的子树里没有左孩子，那么跳出内层 while 循环之后，紧接着被纳入 res 结果数组的就是这个右孩子本身，符合 根->右 的序列规则

关于二叉树的先、中、后序遍历，你对自己的要求应该是能够默写，也就是说要对上面这些逻辑充分熟悉、深刻记忆。

层序遍历的衍生问题

大家看到层序遍历就应该条件反射出 BFS+队列 这对好基友。

题目描述：给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

  3
 / \
9  20
  /  \
 15   7

结果

[
[3],
[9,20],
[15,7]
]
function levelOrderTrans(root) {
  const result = [];
  const queue = [];
  if (root) {
    queue.push(root);
    while (queue.length) {
      const len = queue.length;
      const curLevel = [];
      for (let i = 0; i < len; i++) {
        const node = queue.shift();
        curLevel.push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
      }
      result.push(curLevel);
    }
  }
  return result;
}

翻转二叉树

题目描述：翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

思路分析

一棵二叉树，经过翻转后会有什么特点？答案是每一棵子树的左孩子和右孩子都发生了交换。既然是“每一棵子树”，那么就意味着重复，既然涉及了重复，就没有理由不用递归

function invertTree(root) {
  if (!root) return root;
  // 递归交换左孩子的子结点

  const left = invertTree(root.left);
  // 递归交换右孩子的子结点

  const right = invertTree(root.right);

  // 交换当前遍历到的两个左右孩子结点
  root.left = right;
  root.right = left;
  return root;
}