【Day 53 】2023-08-01 - Top-View-of-a-Tree

[azl397985856]

Top-View-of-a-Tree

入选理由

暂无

题目地址

https://binarysearch.com/problems/Top-View-of-a-Tree

前置知识

暂无

题目描述

Given a binary tree root, return the top view of the tree, sorted left-to-right.

Constraints

n ≤ 100,000 where n is the number of nodes in root

[HuiyingC]

lc - 314. Binary Tree Vertical Order Traversal

思路

• Tag: #Tree, #BFS
• in-order遍历tree
• tree 映射至 x 轴 >> 坐标记录左右信息

• 要什么样的view都可✅ Code

  def verticalOrder(self, root):
  # 队列存nodes
  # column存projection信息
  # 如果project到相同的column, 自动append到一个list
  columnTable = collections.defaultdict(list)
  queue = deque([(root, 0)]) #[node, x]
  
  while queue: #pre-order BFS
      node, column = queue.popleft()
  
      if node:
          columnTable[column].append(node.val) 
          if node.left:
              queue.append((node.left, column - 1))
          if node.right:
              queue.append((node.right, column + 1))
  
  return [columnTable[x] for x in sorted(columnTable.keys())]

  Complexity \ Time : O(nlgn) << sorted() \ Space: O(n)

[Diana21170648]

思路

BFS双端队列插入删除方便 哈希表存储未被占用的值

代码

from collections import deque
class Solution:
    def solve(self,root):
        queue=collections.deque([root,0])
        seen={}
        while queue:
            cur,pos=queue.popleft()
            if pos not in seen:
                seen(pos)=cur.value
            if cur.left:
                queue.append(cur.left,pos-1)
            if cur.right:
                queue.append(cur,right,pos+1)
        return list(map(lambda x:x[1],sorted(seen.items(),key=lambda x:x[0])))#按键值排序的value值

复杂度分析

• 时间复杂度：O(NlogN)，其中 N 为二叉树节点个数，使用了排序。
• 空间复杂度：O(N)，使用了哈希表

[jackgaoyuan]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type Node struct {
    Row   int
    Value int
}

// NodeMap: { [col]: [val1, val2] }
type NodeMap map[int][]Node

func (nodeMap NodeMap) GetResult() [][]int {
    keys := make([]int, 0, len(nodeMap))
    result := make([][]int, 0, len(nodeMap))

    for k := range nodeMap {
        keys = append(keys, k)
    }
    sort.Ints(keys)
    for _, k := range keys {
        var list []int
        nodeList := nodeMap[k]
        sort.Slice(nodeList, func(i, j int) bool {
            if nodeList[i].Row < nodeList[j].Row {
                return true
            } else if nodeList[i].Row > nodeList[j].Row {
                return false
            } else if nodeList[i].Value < nodeList[j].Value {
                return true
            } else {
                return false
            }
        })
        for _, n := range nodeList {
            list = append(list, n.Value)
        }
        result = append(result, list)
    }
    return result
}

func traverTree(node *TreeNode, row, col int, nodeMap NodeMap) {
    // 递归结束条件，如果节点不存在则返回
    if node == nil {
        return
    }
    // 将当前 node 信息添加进 nodeMap 中
    if v, ok := nodeMap[col]; !ok {
        nodeMap[col] = []Node{Node{Row: row, Value: node.Val}}
    } else {
        nodeMap[col] = append(v, Node{Row: row, Value: node.Val})
    }
    traverTree(node.Left, row+1, col-1, nodeMap)
    traverTree(node.Right, row+1, col+1, nodeMap)
}

func verticalTraversal(root *TreeNode) [][]int {
    nodeMap := NodeMap{}
    traverTree(root, 0, 0, nodeMap)
    return nodeMap.GetResult()
}

[Alexno1no2]

#记录每一个列出现的所有数字(带行数)，按列排序，按行排序，按值排序即可。
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())]

[Beanza]

def verticalOrder(self, root):

队列存nodes

# column存projection信息
# 如果project到相同的column, 自动append到一个list
columnTable = collections.defaultdict(list)
queue = deque([(root, 0)]) #[node, x]

while queue: #pre-order BFS
    node, column = queue.popleft()

    if node:
        columnTable[column].append(node.val) 
        if node.left:
            queue.append((node.left, column - 1))
        if node.right:
            queue.append((node.right, column + 1))

return [columnTable[x] for x in sorted(columnTable.keys())]

[Fuku-L]

987. 二叉树的垂序遍历

代码

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

[snmyj]

class Solution:
    def solve(self, root):
        q = collections.deque([(root, 0)])
        d = {}
        while q:
            cur, pos = q.popleft()
            if pos not in d:
                d[pos] = cur.val
            if cur.left:
                q.append((cur.left, pos - 1))
            if cur.right:
                q.append((cur.right, pos + 1))
        return list(map(lambda x:x[1], sorted(d.items(),key=lambda x: x[0])))