【基础篇 - Day 18】 2023-03-02 - 987. 二叉树的垂序遍历 （03. 树 ）

[threedayAAAAA]

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (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 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。  

提示：

树中结点数目总数在范围 [1, 1000] 内 0 <= Node.val <= 1000

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[threedayAAAAA]

思路

dfs，每次都将当前节点的垂系坐标以及深度进行记录，最后排序下即可

代码

function verticalTraversal(root: TreeNode | null): number[][] {
    const orderDataMap: Record<string, Record<string, number[]>> = {}
    function help(node: TreeNode | null, cur: number, dep: number){
        if(!node) return
        const orderData = orderDataMap[cur] ?? {}
        const depData = orderData[dep] ?? []
        depData.push(node.val)
        orderData[dep] = depData
        orderDataMap[cur] = orderData
        node.left && help(node.left, cur - 1, dep + 1)
        node.right && help(node.right, cur + 1, dep + 1)
    } 
    help(root, 0, 0)
    return orderMapDataByKey(orderDataMap).map(item => {
        return orderMapDataByKey(item)
            .reduce((pre, item) => pre.concat(item.sort((a, b) => a - b)), [])
    })
};

function orderMapDataByKey(data: Record<string, any>): Array<any>{
    return Object.entries(data)
        .sort((a, b) => Number(a[0]) - Number(b[0]))
        .map(item => item[1])
}

时空复杂度

• 时间复杂度： O(NlogN)
• 空间复杂度： O(N)

[MiumMi]

思路

1. 按深度遍历，缓存同一列的数据（当前值和行号）

2. 遍历完成之后，按照题意，列最小的在前面，所以对列的大小进行排序取值即可，这里注意下，同一列中可能有相同的值或者同一行的值，这里针对每一列再做一层排序，如果行号不一样则在同一列里面按照行号大小排序，如果行号也是一样的，则按照值的大小排序

   代码

   
   /**
   * Definition for a binary tree node.
   * class TreeNode {
   *     val: number
   *     left: TreeNode | null
   *     right: TreeNode | null
   *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
   *         this.val = (val===undefined ? 0 : val)
   *         this.left = (left===undefined ? null : left)
   *         this.right = (right===undefined ? null : right)
   *     }
   * }
   */

function verticalTraversal(root: TreeNode | null): number[][] { const colMap = {}; const diff = (node: TreeNode | null, row: number, col: number) => { if (!node) { return; } if (!colMap[col]) { colMap[col] = []; } colMap[col].push({ val: node.val, row: row, }); if(node.left) { diff(node.left, row + 1, col - 1); } if (node.right) { diff(node.right, row + 1, col + 1); } }; diff(root, 0, 0); return colSort(colMap); };

// 列排序，按照key的大小值排序即可 function colSort (colMap) { return Object.keys(colMap) .sort((a, b) => Number(a) - Number(b)) .map(item => { return colMap[item] .sort((a, b) => { // 如果行不一样，优先用行排序，否则用当前val值排序 if (a.row !== b.row) { return a.row - b.row; } return a.val - b.val; }) .map(node => node.val); }); }

---
### 分析

[MiumMi]

时间复杂度：?存疑 空间复杂度：O(n)

[yunliuyan]

思路

• 层次遍历，用哈希表储存当前y值和当前的节点值数组
• 层次遍历要将每层遍历，所以每次遍历之前，获取当前队列的长度，就是每一层的节点
• 这时候，要建立一个临时hash表，用来储存当前y值与节点值数组，若y值相等，则在同一个数组中进行排序
• 每次层次遍历完，将临时hash表的值塞入大的hash表中
• 后面排序哈希表的key值，抛出去即可

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
interface QueueItem {
  x: number;
  y: number;
  node: TreeNode;
}

function verticalTraversal(root: TreeNode | null): number[][] {
  const doubleArr: number[][] = [];
  const hashMap: Map<number, number[]> = new Map();
  const queue: QueueItem[] = [];
  if (root) {
    queue.unshift({
      x: 0,
      y: 0,
      node: root
    });
  }

  while(queue.length) {
    const levelLen = queue.length;
    // 缓存每一层的节点值, x轴都相等
    const tempHash: Map<number, number[]> = new Map();
    for (let i = 0; i < levelLen; i++) {
      const curNode = queue.pop()!;
      const { x, y, node } = curNode;
      const tempKey = y;
      // 如果已存在，说明x,y都相等，这时候就要降序排序
      if (tempHash.has(tempKey)) {
        const tempVal = tempHash.get(tempKey)!;
        tempVal.push(node.val)
        tempHash.set(tempKey, tempVal.sort((a, b) => a- b));
      } else {
        tempHash.set(tempKey, [node.val]);
      }
      if(node?.left) {
        queue.unshift({x: x + 1, y: y - 1, node: node.left });
      }
      if (node?.right) {
        queue.unshift({x: x + 1, y: y + 1, node: node.right })
      }
    }
    // 将临时储存的当前层的节点值，赋值到垂直哈希表中
    const tempKeys = Array.from(tempHash.keys());
    for (const key of tempKeys) {
      const tempVal = tempHash.get(key)!;
      if (hashMap.has(key)) {
        let hashVal = hashMap.get(key);
        hashMap.set(key, (hashVal ?? []).concat(tempVal));
      } else {
        hashMap.set(key, tempVal);
      }
    }
    tempHash.clear();
  }
  // 垂直哈希表，进行排序输出即可
  const hashKeys = Array.from(hashMap.keys()).sort((a, b) => a - b);
  for(const key of hashKeys) {
    doubleArr.push(hashMap.get(key)!);
  }

  return doubleArr;
};

复杂度分析

• 时间复杂度: O(nlogn)
• 空间复杂度: O(n)