【Day 18 】2021-09-27 - 987. 二叉树的垂序遍历

[azl397985856]

987. 二叉树的垂序遍历

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree

前置知识

• DFS
• 排序

  题目描述

  
  给定二叉树，按垂序遍历返回其结点值。

对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。

把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（Y 坐标递减）。

如果两个结点位置相同，则首先报告的结点值较小。

按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。

示例 1：

输入：[3,9,20,null,null,15,7] 输出：[[9],[3,15],[20],[7]] 解释： 在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)： 然后，值为 9 的结点出现在 (-1, -1)； 值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)； 值为 20 的结点出现在 (1, -1)； 值为 7 的结点出现在 (2, -2)。 示例 2：

输入：[1,2,3,4,5,6,7] 输出：[[4],[2],[1,5,6],[3],[7]] 解释： 根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。 然而，在报告 "[1,5,6]" 中，结点值 5 排在前面，因为 5 小于 6。

提示：

树的结点数介于 1 和 1000 之间。 每个结点值介于 0 和 1000 之间。

[LOVEwitch]

/**

• 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 hashMap = new Map(); dfs(root, 0 , 0, hashMap); const keyY = [...hashMap.keys()].sort((a,b) => a-b); const res = []; keyY.forEach(x => { const tempRes = []; const tempMap = hashMap.get(x); const keyX = [...tempMap.keys()].sort((a,b) => a-b); keyX.forEach(y => { tempRes.push(...tempMap.get(y).sort((a,b) => a-b)); }) res.push(tempRes); }); return res; };

var dfs = function(root, x, y, hashMap) { if(root === null) return []; if(hashMap.get(y)){ if(hashMap.get(y).get(x)){ hashMap.get(y).get(x).push(root.val); } else { hashMap.get(y).set(x, [root.val]); } } else { hashMap.set(y, new Map().set(x, [root.val])); } if(root.left) dfs(root.left, x+1, y-1, hashMap) if(root.right) dfs(root.right, x+1, y+1, hashMap) }

[yan0327]

思路： 今天又是抄答案的一天，关键点两个。 1.定义一个结构体，按照 列、行、值赋值 在函数内写DFS，并把所有节点放进一个数组。

dfs = func(node *TreeNode, row, col int){
        if node == nil{
            return
        }
        nodes = append(nodes, data{col, row, node.Val})
        dfs(node.Left, row+1, col-1)
        dfs(node.Right, row+1, col+1)
    }
    dfs(root, 0, 0)

2。对该结构体排序，先列升序，再行升序，最后是值升序

sort.Slice(nodes, func(i, j int) bool{
        a, b := nodes[i], nodes[j]
        return a.col < b.col|| a.col == b.col &&(a.row < b.row || a.row == b.row && a.val < b.val)
    })

3.最后是将一维数组转换为二维数组，先判断列是否相等，不等则新增一个数组nil插入二维数组，同时给这个数组append

    lastCol := math.MinInt32
    for _, node := range nodes{
        if node.col != lastCol{
            lastCol = node.col
            ans = append(ans, nil)
        }
        ans[len(ans)-1] = append(ans[len(ans)-1], node.val)
    }
    return ans

type data struct{
    col,row,val int
 }
func verticalTraversal(root *TreeNode) [][]int {
    ans := make([][]int,0)
    nodes := []data{}
    var dfs func(*TreeNode, int, int)
    dfs = func(node *TreeNode, row, col int){
        if node == nil{
            return
        }
        nodes = append(nodes, data{col, row, node.Val})
        dfs(node.Left, row+1, col-1)
        dfs(node.Right, row+1, col+1)
    }
    dfs(root, 0, 0)
    sort.Slice(nodes, func(i, j int) bool{
        a, b := nodes[i], nodes[j]
        return a.col < b.col|| a.col == b.col &&(a.row < b.row || a.row == b.row && a.val < b.val)
    })
    lastCol := math.MinInt32
    for _, node := range nodes{
        if node.col != lastCol{
            lastCol = node.col
            ans = append(ans, nil)
        }
        ans[len(ans)-1] = append(ans[len(ans)-1], node.val)
    }
    return ans
}

时间复杂度：O(n) 空间复杂度:O(n)

[Kashinggo]

思路

基本思路是，行号、列号、节点值存储到哈希表中，按照列号从小到大、行号从小到大、值从小到大的规则排序，填充答案。 但代码不会写QAQ

代码

class Solution {
    Map<TreeNode, int[]> map = new HashMap<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        map.put(root, new int[]{0, 0, root.val});
        dfs(root);
        List<int[]> list = new ArrayList<>(map.values());
        Collections.sort(list, (a, b)->{
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        int n = list.size();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; ) {
            int j = i;
            List<Integer> tmp = new ArrayList<>();
            while (j < n && list.get(j)[0] == list.get(i)[0]) tmp.add(list.get(j++)[2]);
            ans.add(tmp);
            i = j;
        }
        return ans;
    }

    void dfs(TreeNode root) {
        if (root == null) return;
        int[] info = map.get(root);
        int col = info[0], row = info[1], val = info[2];
        if (root.left != null) {
            map.put(root.left, new int[]{col - 1, row + 1, root.left.val});
            dfs(root.left);
        }
        if (root.right != null) {
            map.put(root.right, new int[]{col + 1, row + 1, root.right.val});
            dfs(root.right);
        }
    }
}

复杂度

• 时间：O(N logN) 排序的时间占主导地位
• 空间： O(N) dfs 的栈空间，以及map存储

[laofuWF]

# define a class represent a node with val, x, y
# in order traversal and store node in a dict, update min/max x 
# sort values of in each key-value pair in the dict by x then y then val
# iterate dict by key and add to res
# time: O(NlogN), for sorting
# space: O(N)

class Node:

    def __init__(self, val, x, y):
        self.val = val
        self.x = x
        self.y = y

class Solution:
    def __init__(self):
        self.min_order = float('inf')
        self.max_order = float('-inf')

    def comparator(self, node1, node2):
        if node1.x != node2.x:
            return node1.x - node2.x
        if node1.y != node2.y:
            return node1.y - node2.y
        return node1.val - node2.val

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        order_values = {}

        self.traverse(root, 0, 0, order_values);

        res = []
        temp_min = self.min_order

        for key in order_values:
            order_values[key].sort(key=cmp_to_key(self.comparator))

        while temp_min <= self.max_order:
            if not order_values.get(temp_min):
                continue
            curr_values = []
            for n in order_values.get(temp_min):
                curr_values.append(n.val)
            res.append(curr_values)

            temp_min += 1

        return res

    def traverse(self, node, x, y, order_values):
        if not node:
            return

        curr_list = order_values.get(x, [])
        new_node = Node(node.val, x, y)
        curr_list.append(new_node)
        order_values[x] = curr_list

        self.min_order = min(self.min_order, x)
        self.max_order = max(self.max_order, x)

        self.traverse(node.left, x - 1, y + 1, order_values)
        self.traverse(node.right, x + 1, y + 1, order_values)

[ZJP1483469269]

class Solution { Map<TreeNode, int[]> map = new HashMap<>(); public List<List> verticalTraversal(TreeNode root) { if(root==null) return null; dfs(root,0,0,root.val); List<int[]> list = new ArrayList<>(map.values()); Collections.sort(list, (a, b)->{ return a[0]>b[0]?1:a[0]<b[0]?-1:a[1]>b[1]?1:a[1]<b[1]?-1:a[2]>b[2]?1:a[2]<b[2]?-1:0;

    });
    int n = list.size();
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < n; ) {
        List<Integer> tmp = new ArrayList<>();
        int j=i;
        while(j<n&&list.get(j)[0]==list.get(i)[0]) tmp.add(list.get(j++)[2]);
        ans.add(tmp);
        i = j;
    }
    return ans;

}
public void dfs(TreeNode root,int col,int row,int val){
    map.put(root,new int[]{col,row,val});
    if(root.left!=null)
        dfs(root.left,col-1,row+1,root.left.val);
    if(root.right!=null)
        dfs(root.right,col+1,row+1,root.right.val);
}

}

[aatoe]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
  if (!root) return [];

  // 坐标集合以 x 坐标分组
  const pos = {};
  // dfs 遍历节点并记录每个节点的坐标
  dfs(root, 0, 0);

  // 得到所有节点坐标后，先按 x 坐标升序排序
  let sorted = Object.keys(pos)
    .sort((a, b) => +a - +b)
    .map((key) => pos[key]);

  // 再给 x 坐标相同的每组节点坐标分别排序
  sorted = sorted.map((g) => {
    g.sort((a, b) => {
      // y 坐标相同的，按节点值升序排
      if (a[0] === b[0]) return a[1] - b[1];
      // 否则，按 y 坐标降序排
      else return b[0] - a[0];
    });
    // 把 y 坐标去掉，返回节点值
    return g.map((el) => el[1]);
  });

  return sorted;

  // *********************************
  function dfs(root, x, y) {
    if (!root) return;

    x in pos || (pos[x] = []);
    // 保存坐标数据，格式是: [y, val]
    pos[x].push([y, root.val]);

    dfs(root.left, x - 1, y - 1);
    dfs(root.right, x + 1, y - 1);
  }
};

[muimi]

思路

遍历整个树，将节点按照列存储，排序后输出到结果

代码

class Solution {
  public List<List<Integer>> verticalTraversal(TreeNode root) {
    int leftcol = 0, rightcol = 0;
    List<List<Integer>> res = new ArrayList<>();
    Map<Integer, List<Integer>> map = new HashMap<>();
    Queue<TreeNode> queue = new LinkedList<>();
    Queue<Integer> colQueue = new LinkedList<>();
    queue.add(root);
    colQueue.add(0);
    while (!queue.isEmpty()) {
      int size = queue.size();
      Map<Integer, List<Integer>> sortedMap = new HashMap<>();
      // 同层上的遍历
      while (size-- > 0) {
        // value
        TreeNode node = queue.poll();
        int col = colQueue.poll();
        if (!sortedMap.containsKey(col)) sortedMap.put(col, new ArrayList<Integer>());
        sortedMap.get(col).add(node.val);
        leftcol = Math.min(leftcol, col);
        rightcol = Math.max(rightcol, col);
        // left
        if (node.left != null) { 
          queue.add(node.left);
          colQueue.add(col - 1);
        }
        // right
        if (node.right != null) {
          queue.add(node.right);
          colQueue.add(col + 1);
        }
      }
      // 同层处理完毕，开始排序，排序后加入结果集
      for (int key : sortedMap.keySet()) {
        if (!map.containsKey(key)) map.put(key, new ArrayList<Integer>());
        List<Integer> list = sortedMap.get(key);
        Collections.sort(list);
        map.get(key).addAll(list);
      }
    }
    // Output result
    for (int i = leftcol; i <= rightcol; i++) {
      if (map.containsKey(i)) {
        List<Integer> list = map.get(i);
        res.add(list);
      }
    }
    return res;
  }
}

复杂度

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

[BlueRui]

Problem 987. Vertical Order Traversal of a Binary Tree

Algorithm

• Use BFS to traverse the tree by level.
• Use a TreeMap to store values of each column. column numbers are keys and arrays of node values in this columns are values. The TreeMap naturally sort entries by the natural order of keys.
• Use a PriorityQueue to store the nodes at the same level of BFS. The PriorityQueue has a comparator which sorts nodes by value.
• During traversal, we add column and value of each node to the TreeMap.

Complexity

• Time Complexity: Sorting by PriorityQueue introduces a total time of O(NlogN). Sorting by TreeMap also introduces a total time of O(NlogN). So the total time to solve this problem is O(NlogN).
• Space Complexity: O(N).

Code

Language: Java

class Solution {
    class Node {
        TreeNode node;
        int column;

        Node(TreeNode node, int column) {
            this.node = node;
            this.column = column;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        PriorityQueue<Node> q = new PriorityQueue<>((a, b) -> Integer.compare(a.node.val, b.node.val));

        q.offer(new Node(root, 0));

        while (!q.isEmpty()) {
            PriorityQueue<Node> newQ = new PriorityQueue<>((a, b) -> Integer.compare(a.node.val, b.node.val));

            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node cur = q.poll();
                map.putIfAbsent(cur.column, new ArrayList<>());
                map.get(cur.column).add(cur.node.val);
                if (cur.node.left != null) {
                    newQ.offer(new Node(cur.node.left, cur.column - 1));
                }
                if (cur.node.right != null) {
                    newQ.offer(new Node(cur.node.right, cur.column + 1));
                }
            }
            q = newQ;
        }
        return new ArrayList<List<Integer>>(map.values());
    }
}

[septasset]

思考

分解成2步：

1. BFS给每个节点标row, col
2. 根据标的row,col进行排序，整合

关键点

代码(Python)

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        def bfs_marking(root) -> [tuple]:
            res = []
            queue = collections.deque()
            queue.append((root, 0, 0)) # node, row, col

            while len(queue) > 0:
                node, row, col = queue.popleft()
                res.append((node.val, row, col))
                if node.left is not None:
                    queue.append((node.left, row+1, col-1))
                if node.right is not None:
                    queue.append((node.right, row+1, col+1))
            return res

        node_rcs = bfs_marking(root)
        node_rcs = sorted(node_rcs, key=lambda x: (x[2], x[1], x[0]))

        ans = [[node_rcs[0][0]]]
        col = node_rcs[0][2]
        for i in range(1, len(node_rcs)):
            v,_,c = node_rcs[i]
            if c == col:
                ans[-1].append(v)
            else:
                ans.append([v])
                col = c
        return ans

复杂度分析

• 时间：O（nlogn）
• 空间：O（n）

[lilixikun]

思路

感觉没啥意思、就是记录行号、列、数据、然后各种计算、排序

代码

var verticalTraversal = function(root) {
 const nodeArr = [];

    const getNodeArr = function dfs(root, i, j) {
        if (!root) return;

        nodeArr.push([i, j, root.val]);
        dfs(root.left, i + 1, j - 1);
        dfs(root.right, i + 1, j + 1);
    };

    getNodeArr(root, 0, 0);

    nodeArr.sort((a, b) => {
        if (a[1] !== b[1]) return a[1] - b[1];
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[2] - b[2];
    });

    const resArr = [];
    let lastCol = -1010; // -1000 <= col <= 1000
    for (let i = 0; i < nodeArr.length; ++i) {
        let curCol = nodeArr[i][1];
        if (curCol !== lastCol) {
            lastCol = curCol;
            resArr.push([]);
        }
        resArr[resArr.length - 1].push(nodeArr[i][2]);
    }

    return resArr;
};

[liwangping]

var verticalTraversal = function (root) { const map = new Map();

const getIdx = function dfs(root, i, j) {
    if (!root) return;

    if (!map.has(j)) map.set(j, new Map());
    if (!map.get(j).has(i)) map.get(j).set(i, []);
    map.get(j).get(i).push(root.val);

    dfs(root.left, i + 1, j - 1);
    dfs(root.right, i + 1, j + 1);
};

getIdx(root, 0, 0);

const MAX = 1000,
    resArr = [];
for (let i = -MAX; i <= MAX && resArr.length <= map.size; ++i) {
    if (!map.has(i)) continue;

    resArr.push([]);
    for (let j = -MAX, curM = map.get(i); j <= MAX; ++j) {
        if (curM.has(j)) {
            resArr[resArr.length - 1].push(...curM.get(j).sort((a, b) => a - b));
        }
    }
}

return resArr;

};

[joeytor]

思路

深度优先搜索整个树, 建立一个哈希表, key 是 column 的值, 然后哈希表的 value 是另一个哈希表, key 是 row 的值

递归时传入 row 和 column 的值, 将这个元素添加到 哈希表中

最后遍历 把 column 为 key sorted 的 哈希表, 然后 遍历 把 row 为 key sorted 的哈希表, 将元素的值 sort 之后添加到 list 中, 每次遍历完一个 column 把所以值添加到 result 的 list 中

代码

import collections
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:

        res = collections.defaultdict(dict)

        def traverse(root, row, column):
            if row in res[column]:
                res[column][row].append(root.val)
            else:
                res[column][row] = [root.val]

            if root.left:
                traverse(root.left, row+1, column-1)
            if root.right:
                traverse(root.right, row+1, column+1)

        if not root:
            return []
        else:
            traverse(root, 0, 0)

        output = []
        for k in sorted(res.keys()):
            output_row = []
            res_row = res[k]
            for k_row in sorted(res_row.keys()):
                output_row.extend(sorted(res_row[k_row]))
            output.append(output_row)

        return output

复杂度

n 为树中的元素个数

时间复杂度: O(nlogn), dfs 需要 O(n) 的时间复杂度, 排序 需要 O(nlogn) 的时间复杂度

空间复杂度: O(n), 递归栈最差需要 O(n) 的空间, res 哈希表也需要 O(n) 的空间

[watermelonDrip]

类似树的层序遍历。 在层序遍历的基础上，标记左子树和右子树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        res_col = list()
        # levelOrder 
        def dfs(node,col,row):
            if not node:
                return
            res_col.append([col,row,node.val])
            dfs(node.left, col - 1 ,row +1)
            dfs(node.right,col + 1, row + 1)
        dfs(root,0,0)

        res_col.sort()
        tmp_col = inf
        res = list()
        for col,row, val in res_col:
            if tmp_col != col:
                tmp_col = col
                res.append([])

            res[-1].append(val)
        return (res)

时间复杂度：树的每个节点需要访问一次，O(N) 。 排序O(NlogN) 空间复杂度：栈空间，也就是树的深度O(h)。 res数组需要O(N)

[biscuit279]

思路：先遍历，形成双层字典，再对字典进行排序

class Solution(object):
    def verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        # seen = {}
        seen = collections.defaultdict(
            lambda: collections.defaultdict(list))
        def dfs(root, x=0, y=0):
            if not root:
                return
            # seen[x]={}
            # seen[x][y] =[]
            # seen[x][y].append(root.val)
            seen[x][y].append(root.val)
            # print(seen[0][0])
            dfs(root.left, x-1, y+1)
            dfs(root.right, x+1, y+1)
        dfs(root)
        print(seen)
        ans = []
        #先对x进行排序
        for x_item in sorted(seen.keys()):
            level = []
            #对y进行排序  
            for y_item in sorted(seen[x_item].keys()):
                #对值进行排序
                for v_item in sorted(seen[x_item][y_item]):
                    level.append(v_item)
            ans.append(level)
        return ans

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

[xbhog]

987. 二叉树的垂序遍历

思路：

题解思路，

1. 遍历整棵树，顺带保存每个节点的横纵坐标

2. 根据题意：col,row,value排序

   二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，

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

3. 判断是否属于同一列，是的话加入同列表中

Java代码段：

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<>();
        dfs(root,0,0,nodes);
        //二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，
        //形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
        //先进行题意排序
        Collections.sort(nodes,new Comparator<int[]>(){
            public int compare(int[] t1,int[] t2){
                if(t1[0] != t2[0]){ // col排序
                    return t1[0] - t2[0];
                }else if(t1[1] != t2[1]){ // row排序
                    return t1[1] - t2[1];
                }else{
                    return t1[2] - t2[2];
                }
            }
        });
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int size = 0;
        //排序完成，判断是否属于同一列，是的话加入同列表中
        int temp = Integer.MIN_VALUE;
        for(int[] tt : nodes){
            int col = tt[0],row = tt[1],val = tt[2];
            if(col != temp){
                temp = col;  //更新列值
                res.add(new ArrayList<>());  //不等的话，新增一个列表，加入进去
                size++;
            }
            res.get(size-1).add(val);
        }
        return res;
    }
    //递归遍历树
    public static void dfs(TreeNode root,int col,int row,List<int[]> nodes){
        if(root == null) return;
        nodes.add(new int[]{col,row,root.val});
        dfs(root.left,col-1,row+1,nodes);
        dfs(root.right,col+1,row+1,nodes);
    }
}

复杂度分析：

题解：

时间复杂度：O(nlogn)

其中 n是树中的节点个数。我们需要 O(n) 的时间对整棵树进行一次遍历（例如代码中的深度优先搜索），随后需要 O(nlogn) 的时间对数组 nodes 进行排序，以及 O(n) 的时间对数组 nodes 进行遍历得到最终的答案。由于O(nlogn) 在渐近意义下大于O(n)，所以算法的总时间复杂度为 O(nlogn)。

空间复杂度：O(n) 树中n个节点

[Jding0]

思路

copy from other solutions

python

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        nodes = list()

        def dfs(node: TreeNode, row: int, col: int) -> None:
            if not node:
                return

            nodes.append((col, row, node.val))
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)
        nodes.sort()
        ans, lastcol = list(), float("-inf")

        for col, row, value in nodes:
            if col != lastcol:
                lastcol = col
                ans.append(list())
            ans[-1].append(value)

        return ans

[pan-qin]

idea: use a treemap of integer and treemap to record the coordinates of each node, and use a priority queue to record the node value at the same coordinates; dfs the tree to save everynode in this map, and then output them in order Space: O(n) save each node in the map Time: O(nlogn) sorting

class Solution { public List<List> verticalTraversal(TreeNode root) { TreeMap<Integer, TreeMap<Integer, PriorityQueue>> map = new TreeMap<>(); dfs(root, 0, 0, map); List<List> list = new ArrayList<>(); for (TreeMap<Integer, PriorityQueue> ys : map.values()) { list.add(new ArrayList<>()); for (PriorityQueue nodes : ys.values()) { while (!nodes.isEmpty()) { list.get(list.size() - 1).add(nodes.poll()); } } } return list; } private void dfs(TreeNode root, int x, int y, TreeMap<Integer, TreeMap<Integer, PriorityQueue>> map) { if (root == null) { return; } if (!map.containsKey(x)) { map.put(x, new TreeMap<>()); } if (!map.get(x).containsKey(y)) { map.get(x).put(y, new PriorityQueue<>()); } map.get(x).get(y).offer(root.val); dfs(root.left, x - 1, y + 1, map); dfs(root.right, x + 1, y + 1, map); } }

[littlemoon-zh]

day 18

987. Vertical Order Traversal of a Binary Tree

其实就是自定义排序，如果col相同按照row排，如果row也相同再按照val排，最后按照col的值group一下输出结果，看到有人用TreeMap + PriorityQueue来做，可以但没必要吧。

class Solution {

    List<Integer[]> list = new LinkedList<>();

    public void dfs(TreeNode root, int row, int col) {
        if (root == null)
            return;

        list.add(new Integer[]{col, row, root.val});
        dfs(root.left, row+1, col-1);
        dfs(root.right, row+1, col+1);
    }
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        list.sort(new Comparator<Integer[]>() {
            public int compare(Integer[] o1, Integer[] o2) {
                for (int i = 0; i < 3; i++)
                    if (o1[i] != o2[i])
                        return Integer.compare(o1[i],o2[i]);
                return 0;
            }
        });

        List<List<Integer>> res = new LinkedList<>();

        int last = list.get(0)[0];
        List<Integer> line = new LinkedList<>();

        for (Integer[] li : list) {
            if (last != li[0]) {
                res.add(line);
                last = li[0];
                line = new LinkedList<>();
                line.add(li[2]);
            } else {
                line.add(li[2]);
            }
        }
        res.add(line);
        return res;
    }
}

[JK1452470209]

思路

bfs记录每层坐标等信息，然后用treemap将列，行 值放进map进行排序，然后对其排序

代码

class Solution {
    class treeTemp{
        Integer row;
        Integer col;
        Integer val;

        public Integer getRow() {
            return row;
        }

        public Integer getCol() {
            return col;
        }

        public Integer getVal() {
            return val;
        }

        public treeTemp(Integer row, Integer col, Integer val) {
            this.row = row;
            this.col = col;
            this.val = val;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<treeTemp> treeQueue = new LinkedList<>();
        Map<Integer, TreeMap<Integer, List<Integer>>> map = new TreeMap<>(Comparator.naturalOrder());
        queue.offer(root);
        treeQueue.offer(new treeTemp(0,0,root.val));
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                treeTemp treeTemp = treeQueue.poll();
                map.putIfAbsent(treeTemp.col, new TreeMap<>());
                map.get(treeTemp.col).putIfAbsent(treeTemp.row, new ArrayList<>());
                map.get(treeTemp.col).get(treeTemp.row).add(treeTemp.val);

                if (node.left != null){
                    queue.offer(node.left);
                    treeQueue.offer(new treeTemp(treeTemp.row + 1,treeTemp.col - 1,node.left.val));
                }
                if (node.right != null){
                    queue.offer(node.right);
                    treeQueue.offer(new treeTemp(treeTemp.row + 1,treeTemp.col + 1,node.right.val));
                }
            }
        }

        for (int col : map.keySet()) {
            List<Integer> level = new ArrayList<>();
            for (List list : map.get(col).values()) {
                Collections.sort(list);
                level.addAll(list);
            }
            ans.add(level);
        }

        return ans;
    }
}

复杂度

时间复杂度：O(N)

空间复杂度：O(N)

[benngfour]

思路

1. inorder traverse the tree to get the column, row, value array
2. sort the array
3. generate the result array based the sorted array

語言

JavaScript

Code Solution

var verticalTraversal = function(root) {
    let nodes = [];
    getNodesArr(root, 0, 0, nodes);
    // sort by col first, then row, then node.val
    nodes.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    // generate result array
    let res = [];
    let minCol = -Infinity;
    for (const node of nodes) {
        const col = node[0];
        const val = node[2];
        if (col !== minCol) {
            minCol = col;
            res.push([]);
        }
        res[res.length - 1].push(val)
    } 
    return res;

};

function getNodesArr(root, row, col, nodes) {
    if (root) {
        getNodesArr(root.left, row + 1, col - 1, nodes);
        nodes.push([col, row, root.val]);
        getNodesArr(root.right, row + 1, col + 1, nodes);
    };
}

複雜度分析

• 時間複雜度 O(NlogN)
• 空間複雜度 O(N)

[biancaone]

思路 🏷️

遍历的过程中记录下当前的深度，及左右的相对值。

---

代码 📜

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result = []
        final_result = []

        self.pre_order(root, result, 0, 0)

        result.sort(key = lambda a: (a[1], a[0], a[2]))

        last_col = -sys.maxsize
        for _, y, val in result:
            if y != last_col:
                final_result.append([])
                last_col = y
            final_result[-1].append(val)

        return final_result

    def pre_order(self, root, result, depth, col):
        if not root:
            return
        result.append((depth, col, root.val))
        self.pre_order(root.left, result, depth + 1, col - 1)
        self.pre_order(root.right, result, depth + 1, col + 1)

---

复杂度 📦

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

  ---

[Tao-Mao]

Idea

dfs

Python

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []

        columnTable = defaultdict(list)
        min_column = max_column = 0

        def DFS(node, row, column):
            if node is not None:
                nonlocal min_column, max_column
                columnTable[column].append((row, node.val))
                min_column = min(min_column, column)
                max_column = max(max_column, column)

                DFS(node.left, row + 1, column - 1)
                DFS(node.right, row + 1, column + 1)

        DFS(root, 0, 0)

        ret = []
        for col in range(min_column, max_column + 1):
            ret.append([val for row, val in sorted(columnTable[col])])

        return ret

Complexity

• Time: O(Nlog (N/k)) where kk is the width of the tree.
• Space: O(N)

[james20141606]

Day 18: 987. Vertical Order Traversal of a Binary Tree (binary tree, BFS, DFS)

• Problem Link

  • 987. Vertical Order Traversal of a Binary Tree

• Ideas

  • It is a very classic problem. We need to implement the list/string to BST and reversal process. We could use BFS or DFS.
  • BFS: It is more straightforward for me to use BFS. Use the template, and one thing to note is that for the exact same position (same layer, same vertical position, we should sort the value too). If we only record one vertical position, we need to add another for loop to make sure we are dealing with one layer. Then iterate through pos keys in this layer, sort each position, we could satisfy the needs. Time: O(NlogN); Space: O(N)
  • DFS: We could also use DFS, in DFS, record the x, y position and value. Then after dfs, sort the dict! It is also very straightforward. Note that collections.defaultdict(list) could be used so that if the dict does not have a key, it could initiate an empty list for that new key; Time: O(NlogN); Space: O(N)

• Complexity: (DFS)

  • Time: O(NlogN)
  • Space: O(N)

• Code

#BFS
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        pos = 0
        res = collections.defaultdict(list) 
        q = deque()
        q.append((root,pos))
        prev_pos = 100
        while q:
            restmp = collections.defaultdict(list) 
            #print ('new run' )
            for _ in range(len(q)):
                node,pos = q.popleft()
                if pos in restmp.keys():
                    restmp[pos].append(node.val)
                else:
                    restmp[pos] = [node.val]
                if node.left:
                    q.append((node.left,pos-1))
                if node.right:
                    q.append((node.right,pos+1))
            for key in restmp.keys():
                #for the node in exact same position, should sort the value! we do this by sort the value with same pos(key)  and in the same layer.
                res[key] += sorted(restmp[key])
        return [ res[key] for key in sorted(res.keys()) ]

• other resources:

[jsu-arch]

思路

三重排序。还是在理解代码自己没办法写的阶段。要加油啊。

class Solution(object):
    def verticalTraversal(self, root):
        seen = collections.defaultdict(
            lambda: collections.defaultdict(list))

        def dfs(root, x=0, y=0):
            if not root:
                return
            seen[x][y].append(root.val)
            dfs(root.left, x-1, y+1)
            dfs(root.right, x+1, y+1)

        dfs(root)
        ans = []
        # x 排序、
        for x in sorted(seen):
            level = []
            # y 排序
            for y in sorted(seen[x]):
                # 值排序
                level += sorted(v for v in seen[x][y])
            ans.append(level)

        return ans

Complexity

Time O(nlOg) Space O(n)

[laurallalala]

代码

class Solution(object):
    def verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        nodes = []
        self.dfs(root, nodes, 0, 0)
        nodes.sort()
        res = collections.OrderedDict()
        for col, row, val in nodes:
            if col not in res:
                res[col] = [val]
            else:
                res[col].append(val)
        return res.values()

    def dfs(self, root, nodes, row, col):
        if not root:
            return
        nodes.append((col, row, root.val))
        if root.left:
            self.dfs(root.left, nodes, row+1, col-1)
        if root.right:
            self.dfs(root.right, nodes, row+1, col+1)

复杂度

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[juleijs]

思路

排序

代码

const verticalTraversal = root => {
  const nodeInfos = [];
  getNodeInfos(root, 0, 0);
  nodeInfos.sort((a, b) => a[0] - b[0] || b[1] - a[1] || a[2] - b[2]);
  const map = new Map();
  for (const [x, y, val] of nodeInfos) {
    if (!map.has(x)) msp.set(x, []);
    map.get(x).push(val);
    return [...map.values()];

    const getNodeInfos = (node, x, y) => {
      if (node) {
        getNodeInfos(node.left, x - 1, y - 1);
        nodeInfos.push([x, y, node.val]);
        getNodeInfos(node.right, x + 1, y - 1);
      }
    }
  }
}

复杂度

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

[AgathaWang]

class Solution(object):
    def verticalTraversal(self, root):
        seen = collections.defaultdict(
            lambda: collections.defaultdict(list))

        def dfs(root, x=0, y=0):
            if not root:
                return
            seen[x][y].append(root.val)
            dfs(root.left, x-1, y+1)
            dfs(root.right, x+1, y+1)

        dfs(root)
        ans = []
        # x 排序、
        for x in sorted(seen):
            level = []
            # y 排序
            for y in sorted(seen[x]):
                # 值排序
                level += sorted(v for v in seen[x][y])
            ans.append(level)

        return ans

O(NlogN)

[Daniel-Zheng]

思路

DFS。

代码(C++)

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> nodes;

        function<void(TreeNode*, int, int)> dfs = [&](TreeNode* node, int row, int col) {
            if (!node) {
                return;
            }
            nodes.emplace_back(col, row, node->val);
            dfs(node->left, row + 1, col - 1);
            dfs(node->right, row + 1, col + 1);
        };

        dfs(root, 0, 0);
        sort(nodes.begin(), nodes.end());
        vector<vector<int>> ans;
        int lastcol = INT_MIN;
        for (const auto& [col, row, value]: nodes) {
            if (col != lastcol) {
                lastcol = col;
                ans.emplace_back();
            }
            ans.back().push_back(value);
        }
        return ans;
    }
};

复杂度分析

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

[ningli12]

思路 - 看题解

use a hashmap to record the x-coordinate of the nodes, and record the minX and maxX to get the values use a treemap to record the y-coordinate of the nodes, and use a priorityQueue to keep the ascending order

代码

class Solution {
    Map<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new HashMap<>();
    int minX = 0, maxX = 0;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        helper(root, 0, 0);
        List<List<Integer>> vertical = new ArrayList<>();
        for (int i = minX; i <= maxX; i++) {
            List<Integer> level = new ArrayList<Integer>();
            for (int key : map.get(i).keySet()) {
                while (!(map.get(i).get(key)).isEmpty()) {
                    level.add(map.get(i).get(key).poll());
                }
            }
            vertical.add(level);
        }
        return vertical;

    }

    private void helper(TreeNode node, int x, int y) {
        if (node == null) return;
        minX = Math.min(minX, x);
        maxX = Math.max(maxX, x);
        if (map.get(x) == null) { map.put(x, new TreeMap<Integer, PriorityQueue<Integer>>()); }
        if (map.get(x).get(y) == null) { map.get(x).put(y, new PriorityQueue<Integer>()); }
        map.get(x).get(y).add(node.val);
        helper(node.left, x - 1, y + 1);
        helper(node.right, x + 1, y + 1);   

    }
}

复杂度

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

[Moin-Jer]

思路

---

dfs 记录节点的行、列和值，对三元组进行排序，先排序列，再排序行，最后根据值排序，在排序好的集合中，将列相同的元素的值添加到同一个集合中

代码

---

class Solution {
    Map<TreeNode, int[]> map;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        map = new HashMap<>();
        map.put(root, new int[]{0, 0, root.val});
        dfs(root, 0, 0); 
        ArrayList<int[]> list = new ArrayList<>(map.values());
        Collections.sort(list, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            if (a[1] != b[1]) {
                return a[1] - b[1];
            }
            return a[2] - b[2];
        });
        int len = list.size();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < len; ) {
            int j = i;
            List<Integer> tmp = new ArrayList<>();
            while (j < len && list.get(j)[0] == list.get(i)[0]) {
                tmp.add(list.get(j)[2]);
                ++j;
            }
            ans.add(tmp);
            i = j;
        }
        return ans;
    }

    private void dfs(TreeNode root, int col, int row) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            map.put(root.left, new int[] {col - 1, row + 1, root.left.val});
            dfs (root.left, col - 1, row + 1);
        }
        if (root.right != null) {
            map.put(root.right, new int[] {col + 1, row + 1, root.right.val});
            dfs(root.right, col + 1, row + 1);
        }
    }
}

复杂度分析

---

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

[ginnydyy]

Problem

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

Notes

• It's not a common traversal order for a binary tree. It's required to traverse them from left to right.
• But we can still use common traversal order to traverse the nodes while collect the coordinate information for each node. Then sort the nodes by the coordinate information as required.
• Imagine there is a (x, y) coordinate. The tree root is at (0, 0). If a node is at (x, y), its left child is at (x-1, y-1), its right child is at (x+1, y-1).
• The problem requires to sort the nodes with (x, y) coordinate information as well as the node value. So need to create a new inner class to define the Node type with these information.
• Use BFS or DFS+recursion to traverse the tree, while converting each TreeNode to Node, and put the Node into a list.
• Define a customized comparator, sort the Nodes by Node.x, then Node.y, then Node.val.
• Iterate the sorted list, group the sorted Nodes by Node.x, and put each group of Nodes in a new list.
• Finally put all the lists into the result list.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // tree traversal result
    List<Node> nodeList = new LinkedList<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        // final result
        List<List<Integer>> result = new ArrayList<>();

        // DFS + resucrion traverse the tree and put the traversal result into a list
        helper(root, 0, 0);

        // sort the traversal result by coordinate and value
        Collections.sort(nodeList, new Comparator<Node>(){
                                    public int compare(Node node1, Node node2){
                                        if(node1.x != node2.x){
                                            return node1.x - node2.x;
                                        }
                                        if(node1.y != node2.y){
                                            return node2.y - node1.y;
                                        }
                                        return node1.val - node2.val;
                                    }});

        // group the sorted nodes by node.x and put into the final result
        int currX = nodeList.get(0).x;
        List<Integer> group = new LinkedList<>();
        for(Node node: nodeList){
            if(node.x != currX){
                currX = node.x;
                result.add(group);
                group = new LinkedList<>();
            }
            group.add(node.val);
        }
        result.add(group);

        return result;
    }

    private void helper(TreeNode node, int x, int y){
        if(node ==  null){
            return;
        }

        nodeList.add(new Node(x, y, node.val));
        helper(node.left, x-1, y-1);
        helper(node.right, x+1, y-1);
    }

    class Node{
        int x;
        int y;
        int val;
        public Node(int x, int y, int val){
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }
}

Complexity

• Time: DFS+recursion traversing the tree costs O(n). Sorting the traversal result list costs O(nlogn). Grouping the sorted list and putting into final result costs O(n). Total O(nlogn) (n is the number of tree nodes).
• Space: Recursion extra space is O(h). h is the height of the tree. Worst case h is n. Best case h is logn. Extra space for the traversing result is O(n). Total is O(n).

[ai2095]

LC987. Vertical Order Traversal of a Binary Tree

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

Topics

• Tree

Similar Questions

Hard

Medium

思路

DFS + Dict

代码 Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        d_res = collections.defaultdict(list)
        def recur(root, row, col):
            nonlocal d_res
            if not root:
                return
            d_res[col].append((row, root.val)) 

            recur(root.left, row+1, col-1)
            recur(root.right, row+1, col+1)

        recur(root, 0, 0)

        result = []
        for c in sorted(d_res.keys()):
            result.append([v for k, v in sorted(d_res[c])])
        return result

复杂度分析

时间复杂度： worst: O(NLogN)
空间复杂度：O(N)

[ruohai0925]

题目地址()

题目描述

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        self.res = []  # 把val,row,col直接合并为list中的一项

        def dfs(root, row, col):
            if not root:
                return
            self.res.append([root.val, row, col])  # 注意append的写法
            dfs(root.left, row + 1, col - 1)
            dfs(root.right, row + 1, col + 1)

        def bfs(root):
            q = deque()
            q.append([root, 0, 0])  # 注意append的写法
            while q:
                cur, r, c = q.popleft()
                self.res.append([cur.val, r, c])
                if cur.left:
                    q.append([cur.left, r + 1, c - 1])
                if cur.right:
                    q.append([cur.right, r + 1, c + 1])

        # dfs(root, 0, 0)
        bfs(root)
        self.res.sort(key=lambda x: (x[2], x[1], x[0]))  # sort的精髓，按照多个元素来排序
        # self.res.sort(key=lambda x:(x[2], x[1]))
        res = [[self.res[0][0]]]
        for i in range(1, len(self.res)):  # 循环所有的node
            if self.res[i][2] == self.res[i - 1][2]:
                res[-1].append(self.res[i][0])  # 多在最后一项加一个数值
            else:
                res.append([self.res[i][0]])  # 多加一项
        return res

复杂度分析

• 时间复杂度：搜索：O(n)，排序：O(nlogn)，遍历：O(n)
• 空间复杂度：O(n)

[QiZhongdd]

思路：

• 使用dfs，用数组记录row、col、val
• dfs后进行排序，排序原则先col、row、然后val
• 拍完序后，如果col相同则添加到一个相同的数组

var verticalTraversal = function(root) {
    const nodes = [];
    dfs(root, 0, 0, nodes);
    nodes.sort((tuple1, tuple2) => {
        if (tuple1[0] !== tuple2[0]) {
            return tuple1[0] - tuple2[0];
        } else if (tuple1[1] !== tuple2[1]) {
            return tuple1[1] - tuple2[1];
        } else {
            return tuple1[2] - tuple2[2];
        }
    });

    const ans = [];
    let lastcol = -Number.MAX_VALUE;
    for (const tuple of nodes) {
        let col = tuple[0], row = tuple[1], value = tuple[2];
        if (col !== lastcol) {
            lastcol = col;
            ans.push([]);
        }
        ans[ans.length - 1].push(value);
    }
    return ans;
}

const dfs = (node, row, col, nodes) => {
    if (node === null) {
        return;
    }
    nodes.push([col, row, node.val]);
    dfs(node.left, row + 1, col - 1, nodes);
    dfs(node.right, row + 1, col + 1, nodes);
}

[leolisgit]

思路

题目其实相当于根据col对所有的节点进行分类。

1. dfs，遍历，记录每个节点的行列值
2. 对遍历结果进行排序，列 -> 行 -> 值
3. 对排序结果进行分组，把同一列的分为同一组。

代码

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer[]> list = new ArrayList<>();
        dfs(list, root, 0, 0);

        Collections.sort(list, (a, b) -> {
           if (a[1] != b[1]) {
               return a[1] - b[1];
           }
           if (a[0] != b[0]) {
               return a[0] - b[0];
           }
           return a[2] - b[2]; 
        });

        int lastCol = list.get(0)[1];
        List<Integer> group = new LinkedList<>();

        for (Integer[] node : list) {
            if (node[1] != lastCol) {
                ret.add(group);
                group = new LinkedList<>();
                group.add(node[2]);
                lastCol = node[1];
            } else {
                group.add(node[2]);
            }
        }
        ret.add(group);
        return ret;
    }

    public void dfs(List<Integer[]> list, TreeNode root, int row, int col) {
        if (root == null) {
            return;
        }
        list.add(new Integer[] {row, col, root.val});
        dfs(list, root.left, row + 1, col - 1);
        dfs(list, root.right, row + 1, col + 1);
    }
}

复杂度

时间：O(nlog(n))
空间：O(n)

[florenzliu]

Explanation

• Use hashmap to store all the node values: key - column, value - (row, node.val)
• Use BFS to traverse the tree and store the information of row, column, value in the hashmap
• Use minCol and maxCol to keep track of the minimum column and maxmus column
• Traverse the hashmap keys, and sort each value by row.

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return None
        columnDict = defaultdict(list)
        minCol, maxCol = 0, 0
        queue = [(root, 0, 0)]
        while queue:
            curr, row, col = queue.pop(0)
            if curr:
                columnDict[col].append((row, curr.val))
                minCol = min(minCol, col)
                maxCol = max(maxCol, col)
                queue.append((curr.left, row+1, col-1))
                queue.append((curr.right, row+1, col+1))

        result = []
        for i in range(minCol, maxCol+1):
            currColumn = columnDict[i]
            result.append([val for row, val in sorted(currColumn)])

        return result          

Complexity

• Time Complexity: O(N log(N/k)) where k is the number of the columns in the result
• Space Complexity: O(N)

[chang-you]

Thinking

Sorting data structure: TreeSet, TreeMap, PQ.

Java Code

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                if (o1.x != o2.x) {
                    return o1.x - o2.x;
                } else if (o1.y != o2.y) {
                    return o2.y - o1.y;
                } else {
                    return o1.val - o2.val;
                }
            }
        });

        helper(root, 0, 0, pq);

        int prev = Integer.MIN_VALUE;
        while (!pq.isEmpty()) {
            Point point = pq.poll();
            if (point.x > prev) {
                List list = new ArrayList<>();
                list.add(point.val);
                res.add(list);
            } else {
                List list = res.get(res.size() - 1);
                list.add(point.val);
            }
            prev = point.x;
        }

        return res;
    }

    private void helper(TreeNode root, int x, int y, PriorityQueue pq) {
        if (root == null) {
            return;
        }
        pq.offer(new Point(x, y, root.val));
        helper(root.left, x - 1, y - 1, pq);
        helper(root.right, x + 1, y - 1, pq);
    }

   class Point {
        int x;
        int y;
        int val;
        Point(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    } 
}

Complexity

O(NlogN).

[yanjyumoso]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        # dictionary to store the coordinates of nodes 
        dic=collections.defaultdict(list)
        # node, col, row
        queue = collections.deque([[root, 0, 0]])

        # bfs
        while queue:
            node, c, r = queue.popleft()
            dic[(c, r)].append(node.val)
            if node.left:
                queue.append([node.left, c - 1, r + 1])
            if node.right:
                queue.append([node.right, c + 1, r + 1])

         # sort
        ans, temp = [], []
        currentCol = None
        for j, i in sorted(dic.keys()):
            if j != currentCol:
                ans.append(temp)
                temp = []
                currentCol = j
            temp.extend(sorted(dic[(j, i)]))
        ans.append(temp)
        return ans[1:]

[okbug]

代码

语言： C++

class Solution {
public:
    map<int, vector<vector<int>>> hash;

    void dfs(TreeNode* root, int x, int y) {
        if (!root) return;
        hash[y].push_back({x, root->val});
        dfs(root->left, x + 1, y - 1);
        dfs(root->right, x + 1, y + 1);
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        dfs(root, 0, 0);
        vector<vector<int>> res;
        for (auto& [k, v]: hash) {
            sort(v.begin(), v.end());
            vector<int> col;
            for (auto& p: v) col.push_back(p[1]);
            res.push_back(col);
        }

        return res;
    }
};

[chenming-cao]

解题思路

BFS + 哈希表 + 排序。用一个哈希表储存整个树在不同列的节点值的数组。用BFS对树逐层进行遍历，每一层用另一个哈希表储存该层出现的在不同列的节点值的数组，将数组中的节点值按从小到大排好序后，合并到整棵树的哈希表中。最后将哈希表转换格式输出结果。

代码

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        Map<Integer, List<Integer>> map = new TreeMap<>(); // treemap will sort the keys
        Deque<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));

        while (!queue.isEmpty()) {
            int size = queue.size();
            Map<Integer, List<Integer>> levelMap = new HashMap<>(); // use a map to track node values from the same row and same column
            List<Integer> values;
            List<Integer> levelVals;
            // traverse nodes at each level
            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> nodePair = queue.poll();                
                TreeNode node = nodePair.getKey();
                int col = nodePair.getValue();
                // add node values from the same column to the list of the map
                if (!levelMap.containsKey(col)) {
                    levelVals = new ArrayList<>();
                }
                else {
                    levelVals = levelMap.get(col);
                }
                levelVals.add(node.val);
                levelMap.put(col, levelVals);

                if (node.left != null) {
                    queue.offer(new Pair<>(node.left, col - 1));
                }
                if (node.right != null) {
                    queue.offer(new Pair<>(node.right, col + 1));
                }
            }
            // add results obtained from this row to the result map
            for (int col: levelMap.keySet()) {
                if (!map.containsKey(col)) {
                    values = new ArrayList<>();
                }
                else {
                    values = map.get(col);
                }

                levelVals = levelMap.get(col);
                Collections.sort(levelVals); // sort the node values from the same column and same row
                values.addAll(levelVals); // combine values from the same column
                map.put(col, values);
            }   
        }

        for (int col: map.keySet()) {
            res.add(map.get(col));
        }
        return res;
    }
}

复杂度分析

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

[minuet-red]

class Solution {
public:
    map<int, vector<vector<int>>> hash;

    void dfs(TreeNode* root, int x, int y) {
        if (!root) return;
        hash[y].push_back({x, root->val});
        dfs(root->left, x + 1, y - 1);
        dfs(root->right, x + 1, y + 1);
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        dfs(root, 0, 0);
        vector<vector<int>> res;
        for (auto& [k, v]: hash) {
            sort(v.begin(), v.end());
            vector<int> col;
            for (auto& p: v) col.push_back(p[1]);
            res.push_back(col);
        }

        return res;
    }
};

[flame0409]

987. 二叉树的垂序遍历

思路：首先使用一个三元组，利用dfs取出所有节点，并且保存坐标x，y和值val

接下来根据y，x，val进行排序

最后组成返回链表

class Solution {
    //val,x,y三元组可以唯一确定一个node
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<int[]>();
        //遍历添加节点
        dfs(root, 0, 0, nodes);
        //进行排序
        Collections.sort(nodes, (a, b)->{
            if(a[0] != b[0])return a[0]- b[0];
            if(a[1] != b[1])return a[1]- b[1];
            return a[2] - b[2];
        }
        );
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int size = 0;
        int lastcol = Integer.MIN_VALUE;
        for(int[] node :nodes){
            int y = node[0];
            int x = node[1];
            int v = node[2];
            if(y != lastcol){
                lastcol = y;
                ans.add(new ArrayList<Integer>());
                size++;
            }
            ans.get(size-1).add(v);
        }
        return ans;
    }
    private void dfs(TreeNode root, int x, int y, List<int[]>nodes){
        if(root == null)return;

        nodes.add(new int[]{y, x, root.val});
        dfs(root.left, x + 1, y - 1, nodes);
        dfs(root.right, x + 1, y + 1, nodes);
    }
}

时间复杂度：O(nlogn)，其中 n 是树中的节点个数。进行一次遍历复杂度为O(n)，随后需要 O(nlogn) 的时间对数组 nodes 进行排序，以及 O(n) 的时间对数组 nodes 进行遍历得到最终的答案。由于 O(nlogn) >O(n)，所以算法的总时间复杂度为O(nlogn)。

空间复杂度：O(n)。深度优先搜索中需要 O(n) 的栈空间，同时数组 nodes 也需要O(n) 的空间。

[hewenyi666]

题目名称

987. 二叉树的垂序遍历

题目链接

https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/

题目思路

记录每一个列出现的所有数字(带行数)，按列排序，按行排序，按值排序

code for Python3

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        hashmap = defaultdict(list)
        def dfs(node, x, y):
            if not node:
                return
            hashmap[y].append((x,node.val))
            dfs(node.left, x+1, y-1)
            dfs(node.right,x+1, y+1)

        dfs(root, 0, 0)
        return [list(zip(*sorted(hashmap[i])))[1] for i in sorted(hashmap.keys())]

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[kennyxcao]

987. Vertical Order Traversal of a Binary Tree

Intuition

• BFS
  • level order traversal
  • mark nodes by row and col positions
  • group nodes by col
  • sort nodes within each col by row ascending, then val ascending

Code

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
const verticalTraversal = function(root) {
  if (!root) return [];
  const colToNodes = new Map();
  let minCol = 0;
  let maxCol = 0;
  let queue = [{node: root, row: 0, col: 0}];
  while (queue.length > 0) {
    const nextQueue = [];
    for (const {node, row, col} of queue) {
      if (!colToNodes.has(col)) colToNodes.set(col, []);
      colToNodes.get(col).push({row, val: node.val});
      minCol = Math.min(minCol, col);
      maxCol = Math.max(maxCol, col);
      if (node.left) nextQueue.push({node: node.left, row: row + 1, col: col - 1});
      if (node.right) nextQueue.push({node: node.right, row: row + 1, col: col + 1});
    }
    queue = nextQueue;
  }
  const res = [];
  for (let c = minCol; c <= maxCol; ++c) {
    if (!colToNodes.has(c)) continue;
    const nodes = colToNodes.get(c);
    nodes.sort((a, b) => a.row === b.row ? a.val - b.val : a.row - b.row);
    res.push(nodes.map((node) => node.val));
  }
  return res;
};

Complexity Analysis

• Time: O(n * log(n / k))
• Space: O(n)
• n = num of nodes
• k = num of columns

[Jackielj]

Treemap and PQ

class Solution {
    Map<Integer, TreeMap<Integer, List<Integer>>> map = new TreeMap<>(Comparator.naturalOrder());
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        List<List<Integer>> vertical = new ArrayList<>();
        for (int col : map.keySet()) {
            List<Integer> level = new ArrayList<>();
            for (List list : map.get(col).values()) {
                Collections.sort(list);
                level.addAll(list);
            }
            vertical.add(level);
        }
        return vertical;
    }

    public void dfs(TreeNode root, int col, int row) {
        if (root == null) return;
        map.putIfAbsent(col, new TreeMap<>());
        map.get(col).putIfAbsent(row, new ArrayList<>());
        map.get(col).get(row).add(root.val);
        dfs(root.left, col - 1 , row + 1);
        dfs(root.right, col + 1, row + 1);
        return;
    }
}

时空复杂度

时间: O(nlogn), 因为对TreeMap和PriorityQueue都有O(n)次插入和取出 空间: O(n)

[15691894985]

day 987 二叉树的垂序遍历

https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree

思路：

- 构造（col,row,node）对，表示一个节点，进行DFS
- 先row从左到右，col 从上到下  value从小到大  

        def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
            nodes = list()
            def DFS(col,row,node):
                if not node:
                    return
                nodes.append((col,row,node.val))
                DFS(col-1,row+1,node.left)
                DFS(col + 1,row + 1,node.right)
            # 两次排序，从左到右边，从上到下
            DFS(0,0,root)
            nodes.sort()  #因为是依次按照索引进行排序，所以位置相同时即保证Value值从小到大
            ans , lastcol = list(),float("-inf")
            for col,row,value in nodes:
                if col != lastcol:
                    lastcol = col
                    ans.append(list())
                ans[-1].append(value)
            return ans

复杂度：

- 时间复杂度：O(nlogn)遍历二叉树
- 空间复杂度：深度优先搜索中需要的栈空间，同时node需要O(n)

[xixvtt]

from others' idea:

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result = []
        final_result = []

        self.pre_order(root, result, 0, 0)

        result.sort(key = lambda a: (a[1], a[0], a[2]))

        last_col = -sys.maxsize
        for _, y, val in result:
            if y != last_col:
                final_result.append([])
                last_col = y
            final_result[-1].append(val)

        return final_result

    def pre_order(self, root, result, depth, col):
        if not root:
            return
        result.append((depth, col, root.val))
        self.pre_order(root.left, result, depth + 1, col - 1)
        self.pre_order(root.right, result, depth + 1, col + 1)

Complexcity:

O(n)

[yxq9710]

题目地址(987. 二叉树的垂序遍历)

https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/

前置知识

• 二叉树的遍历

关键点

• 在遍历的时候记录节点的行、列、值信息

  代码

• 语言支持：Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    HashMap<TreeNode, List<Integer>> map;
    List<int[]> finalList;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        //  1. 遍历记录节点信息，包括行信息和列信息以及值信息： 先列后行在值进行排序，即可
        List<List<Integer>> ans = new ArrayList<>();
        map = new HashMap<>();
        finalList = new ArrayList<>();
        dfs(root, 0, 0);
        Collections.sort(finalList, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] == o2[1]){
                    if(o1[0] == o2[0])
                        return o1[2] - o2[2];
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });
        int temp = -1001;
        List<Integer> list = new ArrayList<>();
        for(int[] a: finalList){
            if(a[1] > temp && temp != -1001){
                ans.add(list);
                list = new ArrayList<>();
            }
            list.add(a[2]);
            temp = a[1];
        }
        ans.add(list);
        return ans;

    }

    private void dfs(TreeNode root, int row, int col){
        if(root == null) return;
        int[] temp = new int[]{row, col, root.val};
        finalList.add(temp);
        dfs(root.left, row+1, col-1);
        dfs(root.right, row+1, col+1);
    }
}

复杂度分析

令 n 为数组长度。

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

[Huangxuang]

题目：987. Vertical Order Traversal of a Binary Tree

思路

• 遍历然后排序

代码

class Solution {
    Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        map.put(root, new int[]{0, 0, root.val});
        dfs(root);
        List<int[]> list = new ArrayList<>(map.values());
        Collections.sort(list, (a, b)->{
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        int n = list.size();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; ) {
            int j = i;
            List<Integer> tmp = new ArrayList<>();
            while (j < n && list.get(j)[0] == list.get(i)[0]) tmp.add(list.get(j++)[2]);
            ans.add(tmp);
            i = j;
        }
        return ans;
    }
    void dfs(TreeNode root) {
        if (root == null) return ;
        int[] info = map.get(root);
        int col = info[0], row = info[1], val = info[2];
        if (root.left != null) {
            map.put(root.left, new int[]{col - 1, row + 1, root.left.val});
            dfs(root.left);
        }
        if (root.right != null) {
            map.put(root.right, new int[]{col + 1, row + 1, root.right.val});
            dfs(root.right);
        }
    }
}

复杂度分析

• 时间复杂度：令总节点数量为 nn，填充哈希表时进行树的遍历，复杂度为 O(n)O(n)；构造答案时需要进行排序，复杂度为 O(n\log{n})O(nlogn)。整体复杂度为 O(n\log{n})O(nlogn)
• 空间复杂度：O(n)O(n)

[machuangmr]

思路

• dfs 将数据组装到map中

• 自定义排序，组装返回的结果

  代码

  class Solution {
  Map<TreeNode, int[]> nodeMap = new HashMap<>();
  public List<List<Integer>> verticalTraversal(TreeNode root) {
  // 先将数据装到一个map中，然后按照规则进行排序即可
  
      // int[] 数组的值是col, row, root.val
  
      nodeMap.put(root, new int[]{0, 0, root.val});
      dfs(root);
      List<int[]> nodeList = new ArrayList<>(nodeMap.values());
      Collections.sort(nodeList, (a, b) -> {
          if(a[0] != b[0]) return a[0] -b[0];
          if(a[1] != b[1]) return a[1] -b[1];
          return a[2] - b[2];
      });
      int n = nodeList.size();
      List<List<Integer>> rest = new ArrayList<>();
      for(int i = 0;i < n;) {
          int j = i;
          List<Integer> tmp = new ArrayList<>();
          while(j < n && nodeList.get(j)[0] == nodeList.get(i)[0]) {
              tmp.add(nodeList.get(j)[2]);
              j++;
          }
  
          rest.add(tmp);
          i = j;
      }
      return rest;
  }
  public void dfs(TreeNode root) {
      if(root == null) return;
      int[] info = nodeMap.get(root);
      int col = info[0], row = info[1], val = info[2];
      if(root.left != null) {
          nodeMap.put(root.left, new int[]{col - 1, row + 1, root.left.val});
          dfs(root.left);
      }
      if(root.right != null) {
          nodeMap.put(root.right, new int[]{col + 1, row + 1, root.right.val});
          dfs(root.right);
      }
  }
  }

  复杂度

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