【Day 18 】2022-04-18 - 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 之间。

[ZacheryCao]

Idea

BFS

Code

# 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]]:
        seen = collections.defaultdict(list)
        left, right = 0, 0
        depth = 0
        def bfs(root, row, col):
            nonlocal left, right, depth
            stack = collections.deque()
            stack.append((root, 0, 0))

            while stack:
                l = len(stack)
                depth+=1
                for _ in range(l):
                    cur, row, col = stack.popleft()
                    left = min(left, col)
                    right = max(right, col)
                    seen[(col,row)].append(cur.val)
                    if cur.left:
                        stack.append((cur.left, row+1, col-1))
                    if cur.right:
                        stack.append((cur.right, row+1, col+1))
        bfs(root, 0, 0)
        ans = [[]for _ in range(right - left+1)]
        for i in range(left, right+1):
            for j in range(depth):
                ans[i-left].extend(sorted(seen[(i,j)]))
        return ans

Complexity:

Time: O(N) Space: O(N)

[ZacheryCao]

Idea

DFS. Preorder + HashMap

Code

# 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]]:
        seen = collections.defaultdict(list)
        left, right = 0, 0
        depth = 0
        def dfs(root, col, row):
            nonlocal left, right, depth
            if not root:
                return

            depth = max(depth, row)
            left = min(left, col)
            right = max(right, col)
            seen[(col, row)].append(root.val)
            dfs(root.left, col-1, row+1)
            dfs(root.right, col+1, row+1)

        dfs(root, 0, 0)
        ans = [[]for _ in range(right - left+1)]
        for i in range(left, right+1):
            for j in range(depth+1):
                ans[i-left].extend(sorted(seen[(i,j)]))
        return ans

Complexity:

Time: O(N) Space: O(N)

[forestie9]

Ideas

Store row, col and node value all together

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        def dfs(root, col, row):
            if not root: return
            self.ans[col].append([root.val, row])
            dfs(root.left, col - 1, row+1)
            dfs(root.right, col + 1, row+1)

        self.ans = collections.defaultdict(list)
        dfs(root, 0, 0)
        temp = [sorted(self.ans[key], key = lambda i: (i[1], i[0])) for key in sorted(self.ans.keys())] # use row as second sort
        ans = []
        for item in temp:
            ans.append(i[0] for i in item)
        return ans        

Complexity

O(nlogn) time, O(n) space

[rzhao010]

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>> res = 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]);
            }
            res.add(tmp);
            i = j;
        }
        return res;
    }

    private 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);
        }
    }
}

[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:

[KelvinG-LGTM]

思路

印象里有一个跟这道题差不多的题目, 但是需要写class的.

思路很简单, print每一列的数实际上就是在dic里面记录一下列的信息 (可能为负数), 然后最后整体再"整理"一下. 放入最终结果中.

难点

题目里有这个要求:

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

我们就需要在queue里面同时记录行的信息.

代码

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

        if not root: return []

        queue = deque()
        queue.append((0, 0, root)) # row, col, TreeNode

        while queue: 
            q_len = len(queue)
            for _ in range(q_len): 
                row_idx, col_idx, cur_node = queue.popleft()
                dic[col_idx].append((row_idx, cur_node.val))
                if cur_node.left: 
                    queue.append((row_idx + 1, col_idx - 1, cur_node.left))
                if cur_node.right: 
                    queue.append((row_idx + 1, col_idx + 1, cur_node.right))

        res = [[] for _ in range(len(dic))]
        # print(dic)
        off_set = -min(dic.keys())
        for k, v in dic.items(): 
            tmp = [x[1] for x in sorted(v, key=lambda t: (t[0], t[1]))]
            res[k + off_set] = tmp
        return res

复杂度分析

时间复杂度

O(N) - N: 节点的数量

空间复杂度

O(N) - queue占的地方. 跟N是同一量级

[LyuliangLiu]

Idea

Keep global TreeMap<columnIndex, TreeMap<rowIndex, PriorityQueue>. DFS to traverse and add to map. Do a final pass to add to result list.

Code

class Solution {
    Map<Integer, Map<Integer, List<Integer>>> map = new TreeMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        tranverse(root, 0, 0);
        List<List<Integer>> results = new ArrayList<>();
        for (int col : map.keySet()) {
            Map<Integer, List<Integer>> curColMap = map.get(col);
            List<Integer> newList = new ArrayList<>();
            for (int row : curColMap.keySet()) {
                Collections.sort(curColMap.get(row));
                newList.addAll(curColMap.get(row));
            }
            results.add(newList);
        }
        return results;
    }
    private void tranverse(TreeNode root, int column, int row) {
        if (root == null) {
            return;
        }
        map.putIfAbsent(column, new TreeMap<>());
        Map<Integer, List<Integer>> curCol = map.get(column);
        curCol.putIfAbsent(row, new ArrayList<>());
        curCol.get(row).add(root.val);
        tranverse(root.left, column - 1, row + 1);
        tranverse(root.right, column + 1, row + 1);
    }
}

Complexity

• Time: N[logk + logm + log(N/(km))] = NlogN, k is the number of columns, m the number of rows, therefore N/(km) is the average size of every cell. If we use a global var minColIndex, maxColIndex, then there will be no logk, and time will be N[log(N/k)].
• Space: N + m (递归深度，worst N)

[xixiao51]

Idea

DFS: use DFS preorder traversal to get the (x, y, val) for each node and create a customized class NodePoint to save it. After get the coordinates for all the nodes then sort it by the order of y -> x -> val, then loop once to get the result list.

Code

• DFS:

  class Solution {
  class NodePoint {
      int x;
      int y;
      int val;
  
      public NodePoint(int x, int y, int val) {
          this.x = x;
          this.y = y;
          this.val = val;
      }
  
      public int getX() {
          return x;
      }
  
      public int getY() {
          return y;
      }
  
      public int getVal() {
          return val;
      }
  }
  
  Map<TreeNode, NodePoint> map = new HashMap<>();
  
  public List<List<Integer>> verticalTraversal(TreeNode root) {
      map.put(root, new NodePoint(0, 0, root.val));
      dfs(root);
      List<List<Integer>> res = new ArrayList<>();
      List<NodePoint> points = new ArrayList<>(map.values());
      Collections.sort(points, Comparator.comparing(NodePoint::getY).thenComparing(NodePoint::getX).thenComparing(NodePoint::getVal));
      int y = points.get(0).y;
      int len = points.size();
      for(int i = 0; i < len;) {
          List<Integer> v = new ArrayList<>();
          while(i < len && points.get(i).y == y) {
              v.add(points.get(i++).val);
          }
          if(i < len) {
              y = points.get(i).y;
          }
          res.add(v);
      }
      return res;
  }
  
  private void dfs(TreeNode root) {
      if(root == null) {
          return;
      }
      NodePoint p = map.get(root);
      if(root.left != null) {
          map.put(root.left, new NodePoint(p.x + 1, p.y - 1, root.left.val));
          dfs(root.left);
      }
      if(root.right != null) {
          map.put(root.right, new NodePoint(p.x + 1, p.y + 1, root.right.val));
          dfs(root.right);
      }
  }
  }

Complexity Analysis

• Time complexity: O(NlogN), N is the number of the nodes
• Space complexity: O(N)

[PFyyh]

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

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

题目描述

给你二叉树的根结点 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

前置知识

• 深度遍历
• 数组比较

公司

• 暂无

思路

关键点

• 第一维度是列，第二维度是行，第三维度是值。首先通过深度遍历所有节点，并根据前面的要求排序。
• 然后进行遍历即可。

代码

• 语言支持：Java

Java Code:

class Solution {

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        if (root == null) {
            return null;
        }
        ArrayList<Node> nodes = new ArrayList<>();
        dfs(root, 0, 0, nodes);
        Collections.sort(nodes);
        int maxRow = Integer.MAX_VALUE;
        List<List<Integer>> arrayLists = new ArrayList<>();
        int curIndex = -1;
        int lastCol = Integer.MIN_VALUE;
        for (Node node : nodes) {
            //判断当前是否同列，如果不同列，说明
            if (node.col != lastCol) {
                lastCol = node.col;
                arrayLists.add(new ArrayList<>());
                curIndex++;
            }
            //在同列的基础上，上层在前，下层在后，可以保障
            arrayLists.get(curIndex).add(node.val);
        }
        return arrayLists;
    }

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

    }

}

class Node implements Comparable<Node> {
    int row;
    int col;
    int val;

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

    @Override
    public int compareTo(Node o) {
        //首先保障同列
        if (this.col != o.col) {
            return this.col - o.col;
            //同列的基础上同行
        } else if (this.row != o.row) {
            return this.row - o.row;
            //同行基础上比较值
        } else {
            return this.val - o.val;
        }
    }
}

复杂度分析

n是节点长度，第一次深度遍历，后来一次排序，底层使用二进制插入排序，nlogn,最后还需要遍历一次list

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

[ghost]

思路

从根节点开始，对整棵树进行一次遍历，并在遍历过程中使用数组记录信息

代码

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

复杂度分析

• 时间：O(nlogn)
• 空间：O(n)

[ShawYuan97]

前置知识

• 树的遍历
• 哈希表的哈希表的定义 seen = collections.defaultdict(lambda: collections.defaultdict(list)); seen[x][y] = List

公司

• 暂无

思路

• 首先使用二位哈希表，将行列信息以及val值都存储下来
• 然后依次对列、行进行遍历，将每列的值按照层级关系、值大小关系进行排序

关键点

• 哈希表的哈希表的定义
• 逐层排序

代码

• 语言支持：Python3

Python3 Code:

# 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]]:
        """
        二叉树的垂序遍历，从左到右，从上到下进行输出（上下位置相同时，对值进行排序）
        """
        seen = collections.defaultdict(lambda : collections.defaultdict(list))
        def dfs(root,x,y):
            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,0,0)
        ans = []
        # 按照前序遍历 将节点的行列信息以及val值都存储在一个二维的哈希表中
        # 首先按照列来排序
        for x in sorted(seen):
            level = []
            # 再按照行来排序
            for y in sorted(seen[x]):
                level += sorted(seen[x][y])
            ans.append(level)
        return ans 

复杂度分析

令 n 为数组长度。

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

[MoonLee001]

思路

前序遍历二叉树，记录cloumn、row、val, 按照三个字段从左到右优先级进行排序，然后用map记录下同一cloumn的val,然后转化为数组输出即可.

代码

var verticalTraversal = function(root) {
    let tuples = [];
    const dfs = (root, cloumn, row) => {
        if (root == null) {
            return;
        }
        tuples.push([cloumn, row, root.val]);
        dfs(root.left, cloumn - 1, row + 1);
        dfs(root.right, cloumn + 1, row + 1);
    }
    dfs(root, 0, 0);
    tuples.sort((a, b) => {
        if (a[0] !== b[0]) {
            return a[0] - b[0];
        } else if (a[1] !== b[1]) {
            return a[1] - b[1];
        } else if (a[2] !== b[2]) {
            return a[2] - b[2];
        }
    });

    const map = new Map();
    for (let i = 0; i < tuples.length; i++) {
        const arr = tuples[i];
        if (map.has(arr[0])) {
            map.get(arr[0]).push(arr[2]);
        } else {
            map.set(arr[0], [arr[2]]);
        }
    }
    return Array.from(map.values());
};

复杂度分析

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

[KWDFW]

Day18

987、二叉树的垂序遍历

javascript #树

思路

1、遍历二叉树，并记录每个节点的坐标和值在nodes

2、将nodes中的节点按照列，行，值的顺序升序排序

3、遍历nodes，记录上一次的列号，如果列号不同，则开一个新数组。并向数组中插入值

代码

var verticalTraversal = function(root) {
    let nodes=[]//用来记录所有节点的数组
    function dfs(node,row,col,nodes){//遍历所有节点并记录到nodes中
        if(!node) return null
        nodes.push([col, row, node.val])
        dfs(node.left,row+1,col-1,nodes)
        dfs(node.right,row+1,col+1,nodes)
    }
    dfs(root,0,0,nodes)
    nodes.sort((a,b)=>{//将所有节点按照列，行，值进行升序排序
        if(a[0]!=b[0]){
            return a[0]-b[0]
        }else if(a[1]!=b[1]){
            return a[1]-b[1]
        }else{
            return a[2]-b[2]
        }
    })
    let res=[]//返回的最终数组
    let lastCol=-Number.MAX_VALUE//记录上一次的列号
    for(let n of nodes){//遍历nodes
        if(n[0]!=lastCol){
            lastCol=n[0]
            res.push([])//如果列号不同，就新创建一个数组
        }
        res[res.length - 1].push(n[2])//往res中的最后一个数组中添加值
    }
    return res
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[floatingstarlight]

class Solution { Map<Integer, Map<Integer, List>> map = new TreeMap<>(); public List<List> verticalTraversal(TreeNode root) { tranverse(root, 0, 0); List<List> results = new ArrayList<>(); for (int col : map.keySet()) { Map<Integer, List> curColMap = map.get(col); List newList = new ArrayList<>(); for (int row : curColMap.keySet()) { Collections.sort(curColMap.get(row)); newList.addAll(curColMap.get(row)); } results.add(newList); } return results; } private void tranverse(TreeNode root, int column, int row) { if (root == null) { return; } map.putIfAbsent(column, new TreeMap<>()); Map<Integer, List> curCol = map.get(column); curCol.putIfAbsent(row, new ArrayList<>()); curCol.get(row).add(root.val); tranverse(root.left, column - 1, row + 1); tranverse(root.right, column + 1, row + 1); } }

[TonyLee017]

思路

从根节点开始，对整棵树进行一次遍历（深度优先搜索），在遍历的过程中使用数组nodes记录下每个节点的信息，即行号row，列号col以及值value。然后按照col为第一关键字升序，row为第二关键字升序，value为第三关键字升序，对所有的节点进行排序。最后对nodes进行一次遍历，把同一列的结点放在同一个数组中。

代码

# 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]]:
        # 遍历记录各节点的位置信息
        nodes = list()
        def dfs(node,row,col):
            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
        nodes.sort()
        res,lastcol = list(),float('-inf')
        for col,row,value in nodes:
            if col != lastcol:
                lastcol = col
                res.append(list())
            res[-1].append(value)
        return res

复杂度分析

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

[Magua-hub]

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

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

[hyh331]

Day18 思路

1. 遍历的顺序是先左后右，先上后下，对于行列相同的采取先小后大。
2. 因为要对列排序并把不同的列放在不同的vector里，所以我们可以将它们保存在一个map里面，每个列值对应一个vector。
3. 因为对于列相同的节点，我们对它们的行排序，行相同时还要对它们本身的value排序，所以我们调用STL里的pair帮助排序。pair排序时会先对它的first比对，first相同时再比对second

   class Solution {
   public:
   vector<vector<int>> verticalTraversal(TreeNode* root) {
       dfs(root, 0, 0);     //通过dfs遍历，把节点都安插到mymap里
       vector<vector<int>> ans;  //用于保存答案
       map<int, vector<pair<int, int>>>::iterator itB = myMap.begin(), itE = myMap.end();         //用于遍历mymap
       while(itB != itE){
           vector<pair<int, int>> &col = itB->second;   //取出mymap里的vector<pair>
           sort(col.begin(), col.end());           //对其排序
           const int length = col.size();         //它的长度
           vector<int> tmp(length);              //准备将它转换成vector<int>
           for(int i = 0; i < length; ++i)
               tmp[i] = col[i].second;          //取出值
           ans.push_back(tmp);                   //放入ans
           ++itB;
       }
       return ans;
   }
   private:
   map<int, vector<pair<int, int>>> myMap;  //int是列，vector里存的是该节点的行数和值
   void dfs(TreeNode* root, int row, int col){
       if(root == nullptr)        //空指针就不用搜索下去了
           return;
       myMap[col].push_back({row, root->val}); //加入该列，first是行，second是值
       dfs(root->left, row + 1, col - 1);   //继续搜索
       dfs(root->right, row + 1, col + 1);
   }
   };

   复杂度分析

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

[VictorHuang99]

idea: 对我来说有点难，according to 题解写了一遍 code: 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); }

[carterrr]

package redo.mistakescollection;

import redo.base.TreeNode;

import java.util.*;

/**

• 本质 ： dfs or bfs遍历 + 排序 */ public class 二叉树的垂序遍历_987 {

  public static void main(String[] args) {

  TreeNode _3 = new TreeNode(3);
  TreeNode _9 = new TreeNode(9);
  TreeNode _20 = new TreeNode(20);
  TreeNode _15 = new TreeNode(15);
  TreeNode _7 = new TreeNode(7);
  _3.left = _9;
  _3.right = _20;
  _20.left = _15;
  _20.right = _7;
  Solution solution = new Solution();
  solution.verticalTraversal(_3);

  }

  static class Solution { public List<List> verticalTraversal(TreeNode root) { PriorityQueue<int[]> q = new PriorityQueue<int[]>((a, b) ->{ if(a[0] != b[0]) return a[0] - b[0];// x从小到大 if(a[1] != b[1]) return a[1] - b[1];// y从小到大 return a[2] - b[2]; // val 从小到大 }); dfs(root, q, 0, 0); List<List> res = new ArrayList<>(); while(!q.isEmpty()) { List tmp = new ArrayList<>(); int[] item = q.poll(); tmp.add(item[2]); while(!q.isEmpty() && q.peek()[0] == item[0]) { // 同一列 tmp.add(q.poll()[2]); } res.add(tmp); } return res; }

  private void dfs(TreeNode node, Queue<int[]> queue, int x, int y) {
      if(node == null) return;
      queue.add(new int[]{x,y,node.val});
      dfs(node.left, queue, x - 1, y + 1);
      dfs(node.right, queue, x + 1, y + 1);
  }
  private void bfs(TreeNode node, Queue<int[]> queue, int x, int y) {
  
  }

  } }

[EggEggLiu]

思路

先dfs把所有节点的[val, row, col]存在一个数组里，再根据题目规则排序。最后将排好序的节点数组的val按照规则打包

代码

var verticalTraversal = function(root) {
    let nodes = new Array();
    function dfs(node, row, col) {
        if (!node) {
            return;
        }
        nodes.push([node.val, row, col]);
        dfs(node.left, row + 1, col - 1);
        dfs(node.right, row + 1, col + 1);
    }
    dfs(root, 0, 0);
    function sortNodes(a, b) {
        if (a[2] != b[2]) {
            return a[2] - b[2];
        }
        if (a[1] != b[1]) {
            return a[1] - b[1];
        }
        return a[0] - b[0];
    }
    nodes.sort(sortNodes);
    let res = new Array();
    let start = 0;
    for (let i = 1; i < nodes.length; i++) {
        if (nodes[i][2] != nodes[start][2]) {
            let tmp = new Array();
            for (let j = start; j < i; j ++) {
                tmp.push(nodes[j][0]);
            }
            res.push(tmp);
            start = i;
        }
    }
    let tmp = new Array();
    for (let i = start; i < nodes.length; i++) {
        tmp.push(nodes[i][0]);
    }
    res.push(tmp);
    return res;
};

[kite-fly6618]

思路：

dfs 二维数组保存节点坐标和对应的值，排序

代码：

var verticalTraversal = function(root) {
    if (!root) {
        return [];
    }

    // 二维数组 存坐标和值，形式如 [[x, y, val], [...]]
    let locationList = []; 

    // 先dfs前序遍历记录下节点坐标和值
    const dfs = function(root, x, y) {
        if (!root) {
            return;
        }
        locationList.push([x, y, root.val]);
        dfs(root.left, x - 1, y - 1);
        dfs(root.right, x + 1, y - 1);
    }
    dfs(root, 0, 0);
    // 节点按坐标中的值计算位置，根左子树x-1,y-1,右子树x+1 y-1
    // 按照x升序，y降序，val升序，x不同优先x 什序，若x相同，则y其次，降序排列，若y也相同，则按照节点的值得什序排列
    locationList = locationList.sort((a, b) => {
        if(a[0] != b[0]) {
            return a[0] - b[0];
        }
        if (a[1] != b[1]) {
            return b[1] - a[1]
        }
        return a[2] - b[2];
    });

    // curValOfX当前遍历的节点的x的值，默认先取第一个节点的x值
    let curValOfX = locationList[0][0]; // 第一个节点的x坐标
    let result = [[locationList[0][2]]];// 第一个节点的值

    // 从第2个节点开始遍历坐标数组，把x相同的val分成一组
    for (let i = 1; i < locationList.length; i++) {
        let location = locationList[i];
        let x = location[0];
        if (x == curValOfX) { // x坐标相同，push到同一个数组中
            let last = result[result.length - 1];
            last.push(location[2]);
        } else { // x坐标不同，直接push 一个新数组到result中。由于值已经是按什序排列了，所以进入遍历的顺利，就保证了值按升序排列
            curValOfX = x;
            result.push([location[2]]); 
        }
    }
    return result;
};

复杂度：

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

[flyzenr]

• 思路

  • 见到二叉树，首选使用递归，然后这个题是需要遍历所有结点的，所以我们可以考虑深度优先遍历DFS或者广度优先遍历BFS
  • DFS（递归）
    • 递归，写一个函数，root, root.left, root.right同时满足的规律，用函数dfs来描述
    • 遍历一遍所有节点，遍历的同时记录列表(col,row,value)
    • 遍历完之后，按照col的大小，从小到大排列
    • 然后写一个循环，判断如果col值相等的时候，把值放在相同的列表下，如果不相等，创建一个新列表存入value

• Code - DFS

  -

        # 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]]:
                nodes = list()
                def dfs(node,row,col):
                    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 = list()
                lastcol = float("-inf")
                for col, row, value in nodes:
                    if col != lastcol:
                        lastcol = col
                        ans.append(list())
                    ans[-1].append(value)
  
                return ans

• 复杂度

  • DFS
    • 时间复杂度: $O(nlogn)$ ，n是节点数，排序的复杂度nlogn
    • 空间复杂度 $O(height)$ , 深度

[wychmod]

思路

dict{dict{list[]}} 两个哈希表嵌套，底层是list实现，同时最后用排序dict来实现顺序 第一个键是col，第二个键是row

代码

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        from collections import OrderedDict
        dic = dict()
        def process(root, row, col):
            if not root:
                return
            dic_row = dic.get(col, dict())
            arr = dic_row.get(row, [])
            arr.append(root.val)
            arr.sort()
            dic_row[row] = arr
            dic[col] = dic_row
            process(root.left, row+1, col-1)
            process(root.right, row+1, col+1)

        process(root, 0, 0)
        dic = collections.OrderedDict(sorted(dic.items(), key=lambda t: t[0]))
        res = []
        for key, value in dic.items():
            arr = []
            value = collections.OrderedDict(sorted(value.items(), key=lambda t: t[0]))
            for i, val in value.items():
                arr += val
            res.append(arr)
        return res

复杂度分析

时间复杂度On 空间复杂度On

[CarrieyqZhang]

public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<int[]>();
        dfs(root, 0, 0, nodes);
        Collections.sort(nodes, new Comparator<int[]>() {
            public int compare(int[] tuple1, int[] 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];
                }
            }
        });
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int size = 0;
        int lastcol = Integer.MIN_VALUE;
        for (int[] tuple : nodes) {
            int col = tuple[0], row = tuple[1], value = tuple[2];
            if (col != lastcol) {
                lastcol = col;
                ans.add(new ArrayList<Integer>());
                size++;
            }
            ans.get(size - 1).add(value);
        }
        return ans;
    }

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

time complexity: O(nlogn) space complexity: O(n)

[houmk1212]

思路

用hash表存下每一列的节点，并在插入的时候注意比较大小。

代码

class Solution {
   TreeMap<Integer, TreeMap<Integer, List<Integer>>> map = new TreeMap<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        preDFS(root, 0, 0);
        List<List<Integer>> res = new ArrayList<>();
        for (int col : map.keySet()) {
            List<Integer> tmp = new ArrayList<>();
            for (int row : map.get(col).keySet()) {
                for (int val : map.get(col).get(row)) {
                    tmp.add(val);
                }
            }
            res.add(tmp);
        }
        return res;
    }

    private int findInsertLoc(List<Integer> list, int target) {
        int n = list.size();
        if (n == 0)
            return 0;
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (list.get(mid) >= target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private void preDFS(TreeNode root, int x, int y) {
        if (root == null)
            return;
        if (!map.containsKey(y)) {
            map.put(y, new TreeMap<>());
        }
        if (!map.get(y).containsKey(x)) {
            map.get(y).put(x, new ArrayList<>());
        }
        int loc = findInsertLoc(map.get(y).get(x), root.val);
        map.get(y).get(x).add(loc, root.val);

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

复杂度

• 时间复杂度：O(NlogN)； 遍历N个节点，每个节点都要插入到对应的位置上，用二分法优化为O（logN）
• 空间复杂度：O（N）

[Venchyluo]

3 个要求，column, row(depth), value
按着这个规律排列就好了。

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        # col first, then value
        # because top can botton, level traversal is better
        d = collections.defaultdict(list)
        #col :val[depth]
        minn = float('inf')
        res = []

        queue = collections.deque([[root,0,0]])
        while queue:
            for _ in range(len(queue)):
                node,col,depth = queue.popleft()
                d[col].append([node.val,depth])
                minn = min(minn,col)

                if node.left:
                    queue.append([node.left,col-1,depth+1])
                if node.right:
                    queue.append([node.right,col+1,depth+1])

        while minn in d:
            new = sorted(d[minn], key = lambda x:(x[1],x[0]))
            res.append([x[0] for x in new])
            minn += 1
        return res

time complexity: O(N) 遍历 tree， O(N logN) for sorting space complexity: O(width) for queue, O(N) for result

[YuyingLiu2021]

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

class Solution:
    #def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:     
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        #先用dfs进行遍历 得出每个node的坐标，col，row，val（三元组）
        arr = []
        def dfs(root, row, col):
            if not root:
                return 
            arr.append([col, row, root.val])
            dfs(root.left, row + 1, col - 1)
            dfs(root.right, row + 1, col + 1)
        dfs(root, 0, 0)

        #col 为第一关键字升序， row为第二关键字升序，value为第三关键字升序
        arr = sorted(arr, key=lambda x: (x[0], x[1], x[2]), reverse = False)

        hash_ = defaultdict(list)
        #相同的列存到同一字典里，key为col，value为val
        for i in arr:
            hash_[i[0]].append(i[2])

        res = []
        for i in hash_.values():
            res.append(i)

        return res

[wenliangchen]

Idea

DFS Traversal

code

class Triplet<F, S, T> {
    public final F first;
    public final S second;
    public final T third;

    public Triplet(F first, S second, T third) {
        this.first = first;
        this.second = second;
        this.third = third;
    }
}

class Solution {
    List<Triplet<Integer, Integer, Integer>> nodeList = new ArrayList<>();

    private void DFS(TreeNode node, Integer row, Integer column) {
        if (node == null)
            return;
        nodeList.add(new Triplet(column, row, node.val));
        // preorder DFS traversal
        this.DFS(node.left, row + 1, column - 1);
        this.DFS(node.right, row + 1, column + 1);
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> output = new ArrayList();
        if (root == null) {
            return output;
        }

        // step 1). DFS traversal
        DFS(root, 0, 0);

        // step 2). sort the list by <column, row, value>
        Collections.sort(this.nodeList, new Comparator<Triplet<Integer, Integer, Integer>>() {
            @Override
            public int compare(Triplet<Integer, Integer, Integer> t1,
                    Triplet<Integer, Integer, Integer> t2) {
                if (t1.first.equals(t2.first))
                    if (t1.second.equals(t2.second))
                        return t1.third - t2.third;
                    else
                        return t1.second - t2.second;
                else
                    return t1.first - t2.first;
            }
        });

        // step 3). extract the values, grouped by the column index.
        List<Integer> currColumn = new ArrayList();
        Integer currColumnIndex = this.nodeList.get(0).first;

        for (Triplet<Integer, Integer, Integer> triplet : this.nodeList) {
            Integer column = triplet.first, value = triplet.third;
            if (column == currColumnIndex) {
                currColumn.add(value);
            } else {
                output.add(currColumn);
                currColumnIndex = column;
                currColumn = new ArrayList();
                currColumn.add(value);
            }
        }
        output.add(currColumn);

        return output;
    }
}

Complexity

O(NlogN)

[BiN214]

代码

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
```java

[caterpillar-0]

思路

用DFS遍历树，自定义Node及其优先级，插入优先队列进行排序，然后输出目的数组

代码

class Solution {
public:
        //采用DFS和优先队列，元素被赋予优先级
        //优先队列三个参数，数据类型，容器（必须是以数组实现的），对比仿函数
        //会按照优先级高的元素先出队
        //1、定义排序规则,自定义元素类型并重载<
        struct Node{
            int val,x,y;
            Node(int v,int a,int b):val(v),x(a),y(b){};
            bool operator<(Node n)const{
                if(y!=n.y)return y>n.y;
                else if(x!=n.x)return x>n.x;
                return val>n.val;
            }
        };
        //2、使用unordered_map记录每个元素的行，列及元素值，DFS遍历
        priority_queue<Node> myQueue;
        //通过DFS遍历，填充map
        void dfs(TreeNode* root,int x,int y){
            if(root==nullptr){
                return;
            }
            //插入优先队列，而且按照优先级排序
            myQueue.push({root->val,x,y});
            dfs(root->left,x+1,y-1);
            dfs(root->right,x+1,y+1);      
        }
        //3、返回目标二维数组 
        vector<vector<int>> verticalTraversal(TreeNode* root) {
            vector<vector<int>> res{};
            dfs(root,0,0);
            int i=0;
            while(!myQueue.empty()){
                Node tmp=myQueue.top();//返回栈顶元素
                int row=tmp.y;//当前行
                //!!!!必须先插入一个空数组！！！
                res.push_back(vector<int>());
                while(row==tmp.y && !myQueue.empty()){
                    res[i].push_back(tmp.val);
                    myQueue.pop();
                    tmp=myQueue.top();
                }
                i++;
            }
        return res;
    }
};

复杂度分析

• 时间复杂度：o(nlogn)，插入优先序列排序的时间复杂度
• 空间复杂度：o(n)

[Jongeehsu]

class Solution {
    Map<TreeNode, Integer> node2col = new HashMap<>(), node2row = new HashMap<>();
    Map<Integer, Map<Integer, List<Integer>>> col2row2nodes = new HashMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        node2col.put(root, 0);
        node2row.put(root, 0);
        dfs1(root);
        dfs2(root);
        List<Integer> cols = new ArrayList<>(col2row2nodes.keySet());
        Collections.sort(cols);
        for (int col : cols) {
            Map<Integer, List<Integer>> row2nodes = col2row2nodes.get(col);
            List<Integer> rows = new ArrayList<>(row2nodes.keySet());
            Collections.sort(rows);
            List<Integer> cur = new ArrayList<>();
            for (int row : rows) {
                List<Integer> nodes = row2nodes.get(row);
                Collections.sort(nodes);
                cur.addAll(nodes);
            }
            ans.add(cur);
        }
        return ans;
    }
    // 树的遍历，根据「节点到列」&「节点到行」的映射关系，构造出「从列到行，从行到节点集」的映射关系
    void dfs2(TreeNode root) {
        if (root == null) return ;
        int col = node2col.get(root), row = node2row.get(root);
        Map<Integer, List<Integer>> row2nodes = col2row2nodes.getOrDefault(col, new HashMap<>());
        List<Integer> nodes = row2nodes.getOrDefault(row, new ArrayList<>());
        nodes.add(root.val);
        row2nodes.put(row, nodes);
        col2row2nodes.put(col, row2nodes);
        dfs2(root.left);
        dfs2(root.right);
    }
    // 树的遍历，记录下「节点到列」&「节点到行」的映射关系
    void dfs1(TreeNode root) {
        if (root == null) return ;
        if (root.left != null) {
            int col = node2col.get(root);
            node2col.put(root.left, col - 1);
            int row = node2row.get(root);
            node2row.put(root.left, row + 1);
            dfs1(root.left);
        }
        if (root.right != null) {
            int col = node2col.get(root);
            node2col.put(root.right, col + 1);
            int row = node2row.get(root);
            node2row.put(root.right, row + 1);
            dfs1(root.right);
        }
    }
}

[Ellie-Wu05]

思路一 BFS

根据column，row来记录坐标 然后再sort value 学会了ordereddict： OrderedDict preserves the order in which the keys are inserted. A regular dict doesn’t track the insertion order and iterating it gives the values in an arbitrary order. By contrast, the order the items are inserted is remembered by OrderedDict.

代码

# 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]]:
        node_list = []

        def BFS(root):
            queue = deque([(root, 0, 0)])
            while queue:
                node, row, column = queue.popleft()
                if node is not None:
                    node_list.append((column, row, node.val))
                    queue.append((node.left, row + 1, column - 1))
                    queue.append((node.right, row + 1, column + 1))

        # step 1). construct the global node list, with the coordinates
        BFS(root)

        # step 2). sort the global node list, according to the coordinates
        node_list.sort()

        # step 3). retrieve the sorted results partitioned by the column index
        ret = OrderedDict()
        for column, row, value in node_list:
            if column in ret:
                ret[column].append(value)
            else:
                ret[column] = [value]

        return ret.values()

复杂度分析

时间 Onlogn \ 空间 On

[1973719588]

from collections import deque
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        que1 = deque()
        ls1 = []
        ls2colrow = []
        que2 = deque()

        row = 0
        col = 0

        que1.appendleft(root)
        que2.appendleft(col)

        while que1:
            l = len(que1)
            for _ in range(l):

                node = que1.pop()
                col = que2.pop()
                val = node.val
                ls1.append(val)
                ls2colrow.append([col,row])

                if node.left:
                    que1.appendleft(node.left)
                    que2.appendleft(col-1)

                if node.right:
                    que1.appendleft(node.right)
                    que2.appendleft(col+1)

            row = row + 1

        for i in range(len(ls2colrow)):
            ls2colrow[i].append(ls1[i])

        ls2colrow.sort()

        lsres = []
        lss = []
        a = ls2colrow[0][0]
        lss.append(ls2colrow[0][2])

        for i, _, k in ls2colrow[1:]:

            if i != a:
                a = i
                lsres.append(lss)
                lss = []
                lss.append(k)
            else:
                lss.append(k)

        lsres.append(lss)

        return lsres

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

[sallyrubyjade]

思路

BFS遍历，遍历得到每个节点，并记录下每个节点的row值和column值。先对node数组按按col值排序，再对整个数组进行分组处理。

代码

/**
 * 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) {
    // sortNode逻辑
    // 先按垂序排序，如果垂直相等，按node.val排序
    let sortNode = (nodes) => {
        nodes.sort((a, b) => {
            if (a.row === b.row) {
                return a.val - b.val;
            }
            return a.row - b.row;
        });
        let curArr = [];
        nodes.forEach((cur) => {
            curArr.push(cur.val);
        })
        return curArr;
    }
    // 先BFS
    let queue = [root];
    let nodes = [root];
    root.row = 0;
    root.col = 0;
    while (queue.length) {
        let node = queue.shift();

        if (node.left) {
            node.left.row = node.row + 1;
            node.left.col = node.col - 1;
            queue.push(node.left);
            nodes.push(node.left);
        }
        if (node.right) {
            node.right.row = node.row + 1;
            node.right.col = node.col + 1;
            queue.push(node.right);
            nodes.push(node.right);
        }
    }
    nodes.sort((a, b) => a.col - b.col);
    let ans = [];
    let temp = [];
    for (let i = 0; i < nodes.length; i++) {
        temp.push(nodes[i]);
        if (i != nodes.length - 1) {
            if (nodes[i].col != nodes[i+1].col) {
                ans.push(sortNode(temp));
                temp = [];
            }
        }
    }
    ans.push(sortNode(temp));
    return ans;
};

[linjunhe]

思路

dfs遍历一遍，以col为key，将 (row, val) 存进hashmap； 对col排序后，一列列append到res里（同col的对row排序）

Code

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

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

        dfs(root, 0, 0)
        res = []
        for col in sorted(hashmap.keys()):
            res.append(list(zip(*sorted(hashmap[col])))[1])
        return res

复杂度分析

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

[dzwhh]

【Day 18】987. Vertical Order Traversal of a Binary Tree「二叉树的垂序遍历」

• 题目地址: https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/

题目描述

给你二叉树的根结点 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 在此列中。

前置知识

• dfs
• 哈希表

思路

从根节点开始遍历一次整颗树，在遍历过程中使用数组 nodes 记录每个节点的行号 row， 列号 col以及节点值，遍历完成后对节点进行排序，然后在进行一次遍历，将行号相等的value放在同一个数组

代码

• js 版本

const verticalTraversal = root => {
  const nodes = [];
  dfs(root,0,0,nodes);

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

  const ret = [];
  let min = -Number.MAX_VALUE;
  for(const x of nodes){
    if(min != x[0]){
      min = x[0];
      ret.push([]);
    }
    ret[ret.length - 1].push(x[2]);
  }
  return ret;

  function 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);
  }
}

复杂度分析

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

[xingchen77]

思路

DFS遍历，三层sorted输出

代码

    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        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)

        res = []
        for x in sorted(seen):
            level = []
            for y in sorted(seen[x]):
                level += sorted(v for v in seen[x][y])
            res.append(level)
        return res 

复杂度

时间 O(nlongn) \ 空间 O(n)

[zhiyuanpeng]

class Solution:
    def verticalTraversalHelper(self, root, vals, col, row):
        if root:
            vals.append((col, row, root.val))
            self.verticalTraversalHelper(root.left, vals, col-1, row+1)
            self.verticalTraversalHelper(root.right, vals, col+1, row+1)

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        vals = []
        results = {}
        if root:
            self.verticalTraversalHelper(root, vals, 0, 0)
            vals.sort()
            for comb in vals:
                if comb[0] not in results:
                    results[comb[0]] = [comb[2]]
                else:
                    results[comb[0]].append(comb[2])
            return list(results.values())
        else:
            return []

[JasonHe-WQ]

思路： 层序遍历，每层单独设置一个列表，这一层每个元素记录下一层和它的位置。 然后再判断行，用字典记录重复列的次数，循环取出，排序，再重新加入 代码：

# 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]]:
        q = [root]
        min = 0
        max = 0
        if not root:
            return None
        lo = [[[root.val, 0, 0]]]
        level = 0       
        while q:
            child=[]
            lo.append([])  
            for i in range(len(q)):
                if q[i].left:
                    child.append(q[i].left)
                    lo[-1].append([q[i].left.val, lo[level][i][1] + 1, lo[level][i][2] - 1])
                if q[i].right:
                    child.append(q[i].right)
                    lo[-1].append([q[i].right.val, lo[level][i][1] + 1, lo[level][i][2] + 1])
            q = child
            level += 1
            if not child:
                lo.pop()
        new = []
        for i in lo:
            for j in i:
                new.append(j)
        new = sorted(new,key = lambda x: x[2])
        col = []
        tar = []
        row = {}
        temp = []
        for i in new:
            if i[2] not in col:
                tar.append([])
                col.append(i[2])
                row.clear()
            if i[1]not in row:
                tar[-1].append(i[0])
                row[i[1]] = 1
            else:
                while row[i[1]]>0:
                    temp.append(tar[-1].pop())
                    row[i[1]] -= 1
                temp.append(i[0])
                temp.sort()
                row[i[1]] = len(temp)
                tar[-1].extend(temp)
                temp = []

        return tar         

复杂度： O(nlogn)

[577961141]

513. 找树左下角的值

题目链接

https://leetcode-cn.com/problems/find-bottom-left-tree-value/

题目思路

实际上就是找树的最后一行的左边节点

解法一：

bfs层序遍历:

解法二：

BFS,将每一层的值算出来

题目的题解code

解法一：

使用dfs，直接使用先序遍历或者中序遍历，为什么不是后序遍历，因为左节点一定要比右节点先处理的。用一个变量最大深度，在每次遍寻的时候都要和最大深度比较，如果大于最大深度，就记录最大深度，并且记录当前的值。这样就能找出你想要树的最左子节点的值

<?php

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function findBottomLeftValue($root) {
        $curLeve = [$root];
        $res = $curLeve[0]->val;
        while(count($curLeve)) {
            $nextLeve = [];
            for ($i = 0; $i < count($curLeve); $i++) {
                $curLeve[$i]->left && array_push($nextLeve, $curLeve[$i]->left);
                $curLeve[$i]->right && array_push($nextLeve, $curLeve[$i]->right);
            }
            $res = $curLeve[0]->val;
            $curLeve = $nextLeve;
        }

        return $res;
    }
}

解法二

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution
{
    private $maxDepth = 0;
    private $res = 0;

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function findBottomLeftValue($root)
    {
        $this->res = $root->val;

        $this->dfs($root->left, 0);
        $this->dfs($root->right, 0);
        return $this->res;
    }

    /**
     * dfs遍寻
     *
     * @param $cur
     * @param $depth
     * @author 陈维锐
     * @date 2022/04/18 18:48
     */
    private function dfs($cur, $depth)
    {
        if (!$cur) {
            return;
        }

        $curDepth = $depth + 1;
        if ($curDepth > $this->maxDepth) {
            $this->maxDepth = $curDepth;
            $this->res = $cur->val;
        }

        $this->dfs($cur->left, $curDepth);
        $this->dfs($cur->right, $curDepth);
    }
}

时间和空间复杂度

解法一：

• 时间复杂度：O(n)
• 空间复杂度：O(q),其中q为队列的长度，最坏的情况下为满二叉树，此时和N同阶，其中N为树的节点总数

解法二：

• 时间复杂度：O(n)
• 空间复杂度：O(h)。为树的高度

[L-SUI]

/**
 * 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 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);
}

[zenwangzy]

idea

1.dfs and store the node

2.hashmap key is the x-val ,val is the pair(y-val, val) sorting the 2Dvector, adding the every col with the col order

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

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

### timespace analysis
总的来说，我们需要进行三次排序，分别是对 x 坐标，y 坐标 和 值。

那么时间复杂度是多少呢？我们来分析一下：

哈希表最外层的 key 总个数是最大是树的宽度。

哈希表第二层的 key 总个数是树的高度。

哈希表值的总长度是树的节点数。

也就是说哈希表的总容量和树的总的节点数是同阶的。因此空间复杂度为 O(N)O(N)， 排序的复杂度大致为 NlogNNlogN，其中 N 为树的节点总数。

[Size-of]

思路

dfs + hashmap，dfs先将同列的节点放到一个数组，数组再按同行从小到大排

关键点

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * 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) {
  if (!root) return []
  const collection = {}

  function dfs(node, row = 0, col = 0) {
    if (!node) return

    if (!collection[col]) {
      collection[col] = [[row, node.val]]
    } else {
      collection[col].push([row, node.val])
    }

    dfs(node.left, row + 1, col - 1)
    dfs(node.right, row + 1, col + 1)
  }

  dfs(root)

  let sorted =  Object.keys(collection).sort((a, b) => +a - +b).map(o => collection[o])

  sorted = sorted.map(rows => {
    return rows.sort((a, b) => {
      if (a[0] === b[0]) {
        return a[1] - b[1]
      } else {
        return +a[0] - +b[0]
      }
    }).map(o => o[1])
  })

  return sorted
};

复杂度分析

令 n 为节点个数。

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

[weihaoxie]

思路

1. 用dfs+hashmap,dfs将同列的放到一个数据里面，同列且同行的按照值从小到大排列

2. 按照列数构建返回列表，根据列值顺序将结果放到返回列表中

   代码

   # Definition for a binary tree node.
   # class TreeNode(object):
   #     def __init__(self, val=0, left=None, right=None):
   #         self.val = val
   #         self.left = left
   #         self.right = right
   class Solution(object):
   def getLocate(self,root,locate,row,col):
       if root is not None:
           if col in locate:
               flag = False
               for i in range(len(locate[col])):
                   if row < locate[col][i][1]:
                       locate[col].insert(i,(root.val,row))
                       flag = True
                       break
                   elif row == locate[col][i][1]:
                       if root.val < locate[col][i][0]:
                           locate[col].insert(i,(root.val,row))
                           flag = True
                           break
               if flag== False:
                   locate[col].append((root.val,row))
           else:
               locate[col] = [(root.val,row)]
           self.getLocate(root.left,locate,row+1,col-1)
           self.getLocate(root.right,locate,row+1,col+1)
   
   def verticalTraversal(self, root):
       """
       :type root: TreeNode
       :rtype: List[List[int]]
       """
       locate = {}
       self.getLocate(root,locate,0,0)
       if len(locate) == 0:
           return []
       min_col = 0
       max_col = 0
       temp = {}
       for item in locate:
           if min_col > item:
               min_col = item
           if max_col < item:
               max_col = item
   
       result = [[] for i in range(min_col,max_col+1)]
       for item in locate:
           j = item - min_col
           for data in locate[item]:
               result[j].append(data[0])
       return result

   复杂度

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

[zhishinaigai]

思路

哈希+dfs

代码

typedef pair<int,int> PII;
class Solution {
public:
    map<int,vector<PII>> S;
    void dfs(TreeNode* root,int u,int v){
        if(!root) return;
        S[v].push_back({u,root->val});
        dfs(root->left,u+1,v-1);
        dfs(root->right,u+1,v+1);
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        dfs(root,0,0);
        vector<vector<int>> res;
        for(auto [x,y]:S){
            sort(y.begin(),y.end());
            vector<int> v;
            for(auto a:y) v.push_back(a.second);
            res.push_back(v);
        }
        return res;
    }
};

[miss1]

思路

DFS, 先序遍历，记录每个节点的row和col，存储到map中，map中col为key值，value为对象数组[{row: row, val: root.val}]。

对map的key排序，遍历key获取map的值，将取出来的数组根据row和val的值排序（先比较row的大小，row相同再比较val），再将排序好的数组push到结果数组res中。

map: { 0：[ {row: row, val: root.val} ] }

代码

var verticalTraversal = function(root) {
  let map = new Map();
  let keys = [], res = [];
  let preOrder = function(root, row, col) {
    if (!root) return;
    if (map.has(col)) map.get(col).push({row: row, val: root.val});
    else {
      map.set(col, [{row: row, val: root.val}]);
      keys.push(col);
    }
    preOrder(root.left, row + 1, col - 1);
    preOrder(root.right, row + 1, col + 1);
  };
  preOrder(root, 0, 0);
  keys.sort((a,b) => { return a - b; });
  for (let i = 0; i < keys.length; i++) {
    let arr = map.get(keys[i]);
    arr.sort((a,b) => {
      if (a.row === b.row) return a.val - b.val;
      else return a.row - b.row;
    });
    res.push(arr.map(val => {return val.val}));
  }
  return res;
};

复杂度分析

• time: O(nlogn)
• space: O(n)

[dtldtt]

2022-04-18

987. 二叉树的垂序遍历

思路

先dfs二叉树，把元素按照(col,row,val)的元组的形式存在一个vector中，然后对vector进行排序，按照先col后row后val的升序排列进行排序。也可以不用元组，自定义一个三个元素的struct，然后vector中存放这个struct，并自定义comapare函数，如果col小则小，col一样row小则小，都一样val小则小。最后遍历排序好的vector分别放在结果的vector中。

代码

  #include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

 //* Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode*right) : val(x), left(left), right(right) {}
  };

class Solution {
public:
    vector<tuple<int,int,int>> nodes;
    void dfs(TreeNode *root,int row,int col){
      if(!root) return;
      nodes.emplace_back(col,row,root->val);
      if(root->left) dfs(root->left,row+1,col-1);
      if(root->right) dfs(root->right,row+1,col+1);
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        dfs(root,0,0);
        sort(nodes.begin(),nodes.end());
        vector<vector<int>> ret;
        vector<int> tmp;
        tmp.emplace_back(get<2>(nodes[0]));
        int last_col=get<0>(nodes[0]);
        bool last_flag=false;
        for(int i=1;i<nodes.size();i++){
          if(get<0>(nodes[i])==last_col){
            tmp.emplace_back(get<2>(nodes[i]));
          }
          else{
            ret.push_back(tmp);
            tmp.clear();
            tmp.emplace_back(get<2>(nodes[i]));
            last_col=get<0>(nodes[i]);

          }
          if(i==nodes.size()-1) last_flag=true;
        }
        if(last_flag) ret.push_back(tmp);
      return ret;
    }
};

复杂度分析

• 时间复杂度：O(min(m,n))，其中 m,n 为树节点数。
• 空间复杂度：O(min(m,n))

备注

[freedom0123]

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> nodes = new ArrayList<int[]>();
        dfs(root, 0, 0, nodes);
        Collections.sort(nodes, new Comparator<int[]>() {
            public int compare(int[] tuple1, int[] 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];
                }
            }
        });
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int size = 0;
        int lastcol = Integer.MIN_VALUE;
        for (int[] tuple : nodes) {
            int col = tuple[0], row = tuple[1], value = tuple[2];
            if (col != lastcol) {
                lastcol = col;
                ans.add(new ArrayList<Integer>());
                size++;
            }
            ans.get(size - 1).add(value);
        }
        return ans;
    }

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

[xiayuhui231]

题目

二叉树的垂序遍历 https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/

思路

可以先将所有值及列值放入map中，再依次取出

代码

class Solution {
public:
    map<int, multiset<int>> res;
    void helpr(TreeNode* node,int m, int n){
        if(!node) return ;
        res[m].insert(n*10000+node->val);
        helpr(node->left,m-1,n+1);
        helpr(node->right,m+1,n+1);
        return;
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        helpr(root,0,0);
        vector<vector<int>>num;
        for(auto x:res){
            vector<int>cur;
            for(auto v:x.second){
                cur.push_back(v%10000);
            }
                num.push_back(cur);
        }
        return num;

    }
};

复杂度：

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

[webcoder-hk]

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        self.dict = defaultdict(list)
        def helper(root, row, col):
            if root is None:
                return
            self.dict[col].append((row,root.val))
            helper(root.left, row+1, col-1)
            helper(root.right, row+1, col+1)
        helper(root, 0, 0)
        res = []
        for k in sorted(self.dict.keys()):
            d = sorted(self.dict[k])
            res.append([t[1] for t in d])
        return res

time: O(n) space: O(n)