二叉树的垂序遍历

说在前面

🎈二叉树的遍历方式有很多，前序遍历，中序遍历，后序遍历、层序遍历，这几种遍历方法相信大家都已经很熟悉了吧，那么垂序遍历你们有没有听说过呢？今天让我们一起来看看怎么对二叉树进行垂序遍历。

垂序遍历定义

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

示例 1：

输入： root = [3,9,20,null,null,15,7]
输出： [[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列  1 ：只有结点 20 在此列中。
列  2 ：只有结点 7 在此列中。

示例 2：

输入： root = [1,2,3,4,5,6,7]
输出： [[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列  0 ：结点 1 、5 和 6 都在此列中。
          1 在上面，所以它出现在前面。
          5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列  1 ：只有结点 3 在此列中。
列  2 ：只有结点 7 在此列中。

示例 3：

输入： root = [1,2,3,4,6,5,7]
输出： [[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

思路分析

获取二叉树所有节点

首先我们需要获取到二叉树的所有节点，可以在我们已经很熟悉的前序遍历，中序遍历，后序遍历、层序遍历之中随便选择一种。

这里我们使用层序遍历来获取二叉树中的所有节点，在获取节点的过程中记录每一个节点所在的行和列：

根节点初始化行和列定为（0,0），则其左孩子的行列应该为(-1,2)，右孩子所在的行列应该为（1,2）

层序遍历大家应该都很熟悉了吧：

1. 初始化：

   • 创建一个队列（Queue）用于存放待访问的节点。
   • 将根节点（如果有的话）加入队列。

2. 循环遍历：

   • 当队列不为空时，执行以下步骤：
     • 从队列中取出一个节点（通常称为 current）。
     • 访问 current 节点，这通常意味着执行一些操作，比如打印节点的值。
     • 如果 current 节点有左子节点，将左子节点加入队列。
     • 如果 current 节点有右子节点，将右子节点加入队列。

3. 处理子节点：

   • 对于每个子节点，重复步骤 2，直到队列为空，这意味着所有层的节点都已被访问。

4. 结束：

   • 当队列为空时，层序遍历完成。

const nodeList = [];
const q = [{ node: root, col: 0, row: 0 }];
while (q.length) {
  const { node, col, row } = q.shift();
  nodeList.push({ val: node.val, col: col, row });
  if (node.left) q.push({ node: node.left, col: col - 1, row: row + 1 });
  if (node.right) q.push({ node: node.right, col: col + 1, row: row + 1 });
}

对获取到的所有节点进行排序

按出现位置从上到下排序，如果同行同列上有多个结点，则按结点的值从小到大进行排序。

nodeList.sort((a, b) => {
  if (a.col === b.col && a.row === b.row) {
    return a.val - b.val;
  }
  return a.col - b.col;
});

将排好序的节点按列进行分组

const res = [[nodeList[0].val]];
for (let i = 1; i < nodeList.length; i++) {
  if (nodeList[i].col !== nodeList[i - 1].col) {
    res.push([]);
  }
  res[res.length - 1].push(nodeList[i].val);
}

完整代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
  const nodeList = [];
  const q = [{ node: root, row: 0, col: 0 }];
  //获取二叉树节点集合
  while (q.length) {
    const { node, row, col } = q.shift();
    nodeList.push({ val: node.val, row: row, col });
    if (node.left) q.push({ node: node.left, row: row - 1, col: col + 1 });
    if (node.right) q.push({ node: node.right, row: row + 1, col: col + 1 });
  }
  //对二叉树节点进行排序
  nodeList.sort((a, b) => {
    if (a.row === b.row && a.col === b.col) {
      return a.val - b.val;
    }
    return a.row - b.row;
  });
  //对二叉树节点进行分组
  const res = [[nodeList[0].val]];
  for (let i = 1; i < nodeList.length; i++) {
    if (nodeList[i].row !== nodeList[i - 1].row) {
      res.push([]);
    }
    res[res.length - 1].push(nodeList[i].val);
  }
  return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。