【Day 53 】2022-02-02 - Top-View-of-a-Tree

[azl397985856]

Top-View-of-a-Tree

入选理由

暂无

题目地址

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

前置知识

• BFS
• 哈希表

  题目描述

  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

[feifan-bai]

思路

1. Hash Tree

代码

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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])))

复杂度分析

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

[yetfan]

思路 bfs遍历所有节点，对于每个位置第一次发现的节点进行存储，最后按照位置排序输出。

代码

class Solution:
    def solve(self, root):
        q = collections.deque([(root, 0)])
        value = {}
        while q:  # bfs
            cur, position = q.popleft()
            if position not in value:
                value[position] = cur.val
            if cur.left:
                q.append((cur.left, position - 1))
            if cur.right:
                q.append((cur.right, position + 1))

        return [i for (_, i) in sorted(value.items())]

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

[charlestang]

思路

广度优先遍历 + SortedDict

可以给树的每个节点计算其列编号。然后，用 SortedDict 来排序列。用 BFS 保证节点的出现顺序。

时间复杂度 O(n) 所有节点遍历一遍

空间复杂度 O(W) W 代表二叉树的宽度。

代码

class Solution:
    def solve(self, root):
        from sortedcontainers import SortedDict
        res = SortedDict()
        def bfs(root):
            q = deque([(root, 0)])
            while q:
                newq = []
                while q:
                    n, i = q.popleft()
                    if i not in res:
                        res[i] = n.val
                    if n.left:
                        newq.append((n.left, i - 1))
                    if n.right:
                        newq.append((n.right, i + 1))
                q = deque(newq)
        bfs(root)
        ans = [x for x in res.values()]
        return ans

[ZJP1483469269]

class Solution:
    def solve(self, root):
        dic = {}
        dq = []
        dq.append((root,0))
        while dq:
            x , idx = dq.pop(0)
            if idx not in dic:
                dic[idx] = x.val
            if x.left :
                dq.append((x.left , idx-1))
            if x.right :
                dq.append((x.right , idx+1))

        ls = sorted(dic.items(), key = lambda x : x[0])
        return [x[1] for x in ls]

[ZacheryCao]

Idea

BFS + HashTable

Code:

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
vector<int> solve(Tree* root) {
    map<int, int> coord;
    deque<pair<Tree*,int>> stack;
    stack.push_back(make_pair(root, 0));
    int left=0, right=0;
    while(stack.size()>0){
        pair<Tree*,int> cur = stack.front();
        if(coord.find(cur.second)==coord.end()) coord.insert(make_pair(cur.second, cur.first->val));
        left = min(left, cur.second);
        right = max(right, cur.second);
        stack.pop_front();
        if(cur.first->left!=NULL){
            stack.push_back(make_pair(cur.first->left,cur.second-1));
        }
        if(cur.first->right!=NULL){
            stack.push_back(make_pair(cur.first->right,cur.second+1));
        }
    }
    vector<int> ans;
    for(int i = left; i<= right;i++){
        if(coord.find(i)!=coord.end()){
            ans.push_back(coord[i]);
        }          
    }
    return ans;
}

Complexity:

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

[falconruo]

思路:

广度优先遍历 + 哈希表

复杂度分析:

• 时间复杂度: O(N)， 其中N是树的结点数
• 空间复杂度: O(H)，H为树的深度

代码(C++):

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
vector<int> solve(Tree* root) {
    if (!root) return {};

    map<int, int> mp;
    queue<pair<Tree*, int>> qt;
    qt.push({root, 0}); //{node, x}

    while (!qt.empty()){
        size_t size = qt.size();
        while (size--) {
            pair<Tree*, int> top = qt.front();
            Tree* node = top.first;
            int x = top.second;
            qt.pop();

            if (!mp.count(x))
                mp[x] = node->val;

            if (node->left)
                qt.push({node->left, x - 1});

            if (node->right)
                qt.push({node->right, x + 1});
        }
    }

    vector<int> res;
    for (auto& n : mp)
        res.push_back(n.second);

    return res;
}

[laofuWF]

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# doing dfs for each node formated as (x, value)
# only add to dict when x coord is not visited
# sort by key and append value to res

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

class Solution:
    def solve(self, root):
        queue = [(0, root)]
        visited = {}

        while queue:
            x, node = queue.pop(0)
            if x not in visited:
                visited[x] = node.val
            if node.left:
                queue.append((x - 1, node.left))
            if node.right:
                queue.append((x + 1, node.right))

        sorted_keys = sorted(visited.keys())

        res = []
        for k in sorted_keys:
            res.append(visited[k])

        return res

[zwx0641]

import java.util.*;

/**

• public class Tree {
• int val;
• Tree left;
• Tree right;

• } */ class Solution { public int[] solve(Tree root) { Map<Integer, Integer> positions = new HashMap<>(); Map<Integer, Integer> levels = new HashMap<>(); traverse( root, positions, levels, 0, 0); // Traverse tree and populate 'positions' and 'levels'

  // Get minimum and maximum positions, because Hashmap isn't sorted
  int min = Integer.MAX_VALUE;
  int max = Integer.MIN_VALUE;
  for (Integer key : positions.keySet()) {
      min = Math.min(min, key);
      max = Math.max(max, key);
  }
  
  // Get the corresponding node at each position
  int[] ans = new int[max - min + 1];
  for (int i = min; i <= max; i++) {
      ans[i - min] = positions.get(i);
  }
  return ans;

  }

  public void traverse(Tree root, Map<Integer, Integer> positions, Map<Integer, Integer> levels, int pos, int lvl) { if (root == null) return; if (levels.containsKey(pos)) { // Update 'positions', because the top view would be at the lowest level if (levels.get(pos) > lvl) { positions.put(pos, root.val); levels.put(pos, lvl); } } else { levels.put(pos, lvl); positions.put(pos, root.val); }

  traverse(root.left, positions, levels, pos - 1, lvl + 1);
  traverse(root.right, positions, levels, pos + 1, lvl + 1);

  } }

[zhy3213]

思路

bfs

代码

    def solve(self, root):
        if not root:
            return []
        q=deque([(root,0)])
        res=deque()
        l=0
        r=-1
        while q:
            node,pos=q.popleft()
            if pos>r:
                res.append(node.val)
                r+=1
            elif pos<l:
                res.appendleft(node.val)
                l-=1
            if node.left:q.append((node.left,pos-1))
            if node.right:q.append((node.right,pos+1))
        return list(res)

[CoreJa]

思路

• BFS+哈希：层序遍历树，遍历时标记节点的下标并存到哈希表里，再把哈希表按key顺序返回即可。复杂度$O(n)$
• BFS+双端队列：上述改进，层序遍历树并标记下标，维护两个变量表示ans的左右界，下标超过左右界时在其左右新增元素即可。复杂度$O(n)$

代码

class Solution:
    def solve1(self, root):
        ans = {}
        q = deque([(root, 0)])
        while q:
            node, index = q.popleft()
            if index not in ans:
                ans[index] = node.val
            if node.left:
                q.append((node.left, index - 1))
            if node.right:
                q.append((node.right, index + 1))

        return [ans[i] for i in sorted(ans.keys())]

    def solve(self, root):
        q = deque([(root, 0)])
        ans = deque([root.val])
        left, right = 0, 0
        while q:
            node, index = q.popleft()
            if index < left:
                ans.appendleft(node.val)
                left = index
            elif index > right:
                ans.append(node.val)
                right = index
            if node.left:
                q.append((node.left, index - 1))
            if node.right:
                q.append((node.right, index + 1))

        return list(ans)

[zjsuper]

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

[ZhangNN2018]

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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])))

[Liuxy94]

思路

hashtable +BFS

代码

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
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])))

复杂度分析： 时间：O(n logn)

空间：O(n)

[xinhaoyi]

Top View of a Tree

Top View of a Tree | binarysearch

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

Constraints


思路一

找到树的每个左/右移位的最低深度

用一个包含三个值的哈希图：左移/右移、深度和值。 要将三个值存储在哈希图中，哈希图的值是一个由 depth + " " + root.val 组成的字符串

如果map包含当前节点左移/右移的键，即左移和右移，就比较它的深度，如果它以前的深度高于当前的，那么就用当前节点的深度替换深度和 具有当前节点值的值。

在此之后，我构建了一个map，其中包含映射到其最低深度的所有的键。 只要将所有这些值传输到一个数组中并返回它即可

代码

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    Map<Integer, String> hortotop = new HashMap<>();
    public int[] solve(Tree root) {
        recurse(root, 0, 1);
        int miny = Integer.MAX_VALUE;
        int maxy = Integer.MIN_VALUE;
        for (int i : hortotop.keySet()) {
            miny = Math.min(i, miny);
            maxy = Math.max(i, maxy);
        }
        int[] ret = new int[hortotop.size()];
        int tracker = 0;
        for (int i = miny; i <= maxy; i++) {
            String temp = hortotop.get(i);
            ret[tracker] = Integer.parseInt(temp.substring(temp.indexOf(" ") + 1, temp.length()));
            tracker++;
        }
        return ret;
    }
    public void recurse(Tree root, int hor, int depth) {
        if (root == null)
            return;
        if (!hortotop.containsKey(hor)) {
            hortotop.put(hor, depth + " " + root.val);
        } else {
            String temp = hortotop.get(hor);
            if (Integer.parseInt(temp.substring(0, temp.indexOf(" "))) > depth) {
                hortotop.put(hor, depth + " " + root.val);
            }
        }

        recurse(root.left, hor - 1, depth + 1);
        recurse(root.right, hor + 1, depth + 1);
    }
}

[chen445]

class Solution:
    def solve(self, root):
        q=deque([(root,0)])
        result={}
        while q:
            n=len(q)
            for i in range(n):
                node,label=q.popleft()
                if node:      
                    if label not in result:
                        result[label]=node.val
                        final_result
                    q.append((node.left,label-1))
                    q.append((node.right,label+1))
        all_labels=result.keys())
        final_result=[]
        for i in range(min(all_labels),max(all_labels)+1):
            final_result.append(all_labels[i])
        return final_result

[zhangzz2015]

思路

• 使用BFS，BFS level可以反应从上到下。保证上面先访问，level为row。另外同时记录col。根据col进行排序并可确定是否有更小的row已经访问过。时间复杂度为 O(n)，空间复杂度为 O(n)。

代码

• 语言支持：C++

C++ Code:

vector<int> solve(Tree* root) {
    // BFS. 
    queue<pair<Tree*,int>> que; 
    map<int, int> record; 
    if(root)
      que.push(make_pair(root,0));
    while(que.size())
    {
        int iSize = que.size(); 
        for(int i=0; i< iSize; i++)
        {
            pair<Tree*, int> topNode = que.front(); 
            if(record.count(topNode.second)==0)
            {
                record[topNode.second]=topNode.first->val; 
            }
            que.pop(); 

            if(topNode.first->left)
                que.push(make_pair(topNode.first->left, topNode.second-1)); 
            if(topNode.first->right)
                que.push(make_pair(topNode.first->right, topNode.second+1)); 
        }
    }
    vector<int> ret; 
    for(auto it = record.begin(); it!=record.end(); it++)
    {
        ret.push_back((*it).second); 
    }
    return ret; 

}

[tongxw]

思路

BFS保证从上向下遍历，把节点按纵坐标编号，root节点的纵坐标为0，左右子树分别为-1和1，依次类推。 纵坐标相同时，只第一次出现时对应的节点，所以用Set记录纵坐标的值。

class Solution {
    public int[] solve(Tree root) {
        HashSet<Integer> set = new HashSet<>();
        LinkedList<Integer> ans = new LinkedList<>();
        if (root == null) {
            return new int[0];
        }

        Queue<Data> q = new LinkedList<>();
        q.offer(new Data(root, 0));
        while (!q.isEmpty()) {
            int len = q.size();
            for (int i=0; i<len; i++) {
                Data d = q.poll();

                if (!set.contains(d.col)) {
                    set.add(d.col);
                    if (d.col < 0) {
                        ans.addFirst(d.node.val);
                    } else {
                        ans.addLast(d.node.val);
                    }
                }

                if (d.node.left != null) {
                    q.offer(new Data(d.node.left, d.col - 1));
                }
                if (d.node.right != null) {
                    q.offer(new Data(d.node.right, d.col + 1));
                }
            }
        }

        int[] ret = new int[ans.size()];
        for (int i=0; i<ret.length; i++) {
            ret[i] = ans.get(i);
        }

        return ret;

    }

    private class Data {
        Tree node;
        int col;
        Data(Tree node, int col) {
            this.node = node;
            this.col = col;
        }
    }
}

TC: O(n) SC: O(n)

[dahaiyidi]

Problem

987. 二叉树的垂序遍历

++

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

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

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

返回二叉树的 垂序遍历 序列。

---

Note

• 重要的是要按照col排序
• 注意排序的写法
• 注意C++的写法
  • vector<tuple<int, int, int>> nodes;
  • function<void(TreeNode, int, int)> dfs = [&](TreeNode root, int col, int row){} C++11lambda表达式：https://www.cnblogs.com/DswCnblog/p/5629165.html
  • sort(nodes.begin(), nodes.end());
  • for(const auto& [col, row, val]: nodes)
  • res.emplace_back();

---

Complexity

• 时间O：nlogn 来源于排序的时间
• 空间O：n

---

Python

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

        dfs(root, 0, 0)
        nodes.sort() # 按照col为第一关键字升序，row为第二关键字升序，val为第三关键字升序
        last_col = float('-inf')
        res = []

        for col, row, val in nodes:
            if col != last_col:
                res.append([])
                last_col = col
            res[-1].append(val)
        return res

C++

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> nodes;
        // function写法？
        function<void(TreeNode*, int, int)> dfs = [&](TreeNode* root, int col, int row){
            if(!root){
                return;
            }
            nodes.emplace_back(col, row, root->val);
            dfs(root->left, col - 1, row + 1);
            dfs(root->right, col + 1, row + 1);
        };

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

    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[Tesla-1i]

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])))

[zol013]

class Solution:
    def solve(self, root):
        view = []
        queue = deque([(root, 0)])
        seen = set()

        while queue:
            node, position = queue.popleft()
            if position not in seen:
                view.append((node.val, position))
                seen.add(position)

            if node.left:
                queue.append((node.left, position - 1))
            if node.right:
                queue.append((node.right, position + 1))

        view.sort(key = lambda x:x[1])
        return [val for val, postion in view]

[haixiaolu]

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

[LinnSky]

思路

二叉树的垂序遍历

代码

     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;

[LannyX]

思路

BFS

代码

LeetCode 199
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            int size = q.size();
            TreeNode last = q.peek();
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                if(cur.right != null){
                    q.offer(cur.right);
                }
                if(cur.left != null){
                    q.offer(cur.left);
                }
            }
            res.add(last.val);
        }
        return res;
    }
}

复杂度分析

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

[tian-pengfei]

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
//        <col row,value> 和排序有关系
        vector<tuple<int,int,int>> re;
        function<void(TreeNode*,int,int)> dfs = [&](TreeNode* node,int row,int col  ){
            if(!node){
                return;
            }
            re.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(re.begin(),re.end());
         vector<vector<int>> re2;
        int last_col=INT_MIN;
        for( auto [col,row,val]: re){

            if(col!=last_col){
                last_col = col;
                re2.emplace_back();
            }
                      re2.back().emplace_back(val);
        }
        return re2;

    }
};

[jiaqiliu37]

class Solution:
    def solve(self, root):
        queue = deque([(root, 0)])
        seen = set()
        view = []

        while queue:
            node, position = queue.popleft()
            if position not in seen:
                seen.add(position)
                view.append((node.val, position))
            if node.left:
                queue.append((node.left, position - 1))
            if node.right:
                queue.append((node.right, position + 1))

        view.sort(key = lambda x: x[1])
        return [value for value, position in view]

Time complexity O(nlogn) Space complexity O(n)

[zhiyuanpeng]

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])))

[yan0327]

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
 }

type pair struct {
    node *TreeNode
    x int
}
var dict map[int]int

func bfs(root *TreeNode, dict map[int]int){
    q := []pair{}
    q = append(q,pair{root,0})
    for len(q) > 0{
        kvp := q[0]
        node := kvp.node
        x := kvp.x
        if _,ok := dict[x];!ok{
            dict[x] = node.Val
        }
        q = q[1:]
        if node.Left != nil{
            q = append(q,pair{node.Left,x-1})
        }
        if node.Right != nil{
            q = append(q,pair{node.Right,x+1})
        }
    }
}

func solve(root *TreeNode) []int{
    dict = map[int]int{}
    bfs(root,dict)
    out := []int{}
    min ,max := math.MaxInt32,math.MinInt32
    for x,_ := range dict{
        if x < min{
            min = x
        }
        if x > max{
            max = x
        }
    }
    for i:=min;i<=max;i++{
        out = append(out,dict[i])
    }
    return out
}

[CodingProgrammer]

思路

BFS + Map，层次遍历，根节点的 idx 为0，向左走一位， idx 减1；向右走一位，idx 加1。利用 map（key 为 idx, value为节点值） 记录当前位置第一次遍历到的节点

代码

class Solution {

    public int[] solve(Tree root) {
        if (root == null) return new int[0];
        // key-idx, value-node.val
        Map<Integer, Integer> nodeMap = new HashMap<>();
        Queue<Object[]> nodeQueue = new LinkedList<>();
        nodeQueue.offer(new Object[]{root, 0});
        while (!nodeQueue.isEmpty()) {
            Object[] pair = nodeQueue.poll();
            Tree node = (Tree) pair[0];
            int idx = (int) pair[1];

            if (!nodeMap.containsKey(idx)) {
                nodeMap.put(idx, node.val);
            }

            if (node.left != null) {
                nodeQueue.offer(new Object[]{node.left, idx - 1});
            }

            if (node.right != null) {
                nodeQueue.offer(new Object[]{node.right, idx + 1});
            }
        }

        int[] keys = new int[nodeMap.size()];
        int idx = 0;
        for (int key : nodeMap.keySet()) {
            keys[idx++] = key;
        }
        Arrays.sort(keys);
        int[] res = new int[nodeMap.size()];
        idx = 0;
        for (int key : keys) {
            res[idx++] = nodeMap.get(key);
        }
        return res;
    }
}

复杂度

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

[1149004121]

Top View of a Tree

思路

考虑从根节点看，从左往右的试图，可以将每个结点的坐标标记出来，左节点为[-1,1],右节点为[1,1]，如果横坐标相同，则使用纵坐标小的那个。如果使用层序遍历，则不用考虑其纵坐标，只需考虑是否出现。

代码

class Solution {
  solve(root) {
    let positions = {};
    let queue = [[root, 0]];
    while (queue.length) {
      let [node, x] = queue.shift();
      if (!positions[x]) positions[x] = node;
      if (node.left) queue.push([node.left, x - 1]);
      if (node.right) queue.push([node.right, x + 1]);
    };
    let res = Object.entries(positions).sort((a, b) => a[0] - b[0]).map(item => item[1].val);
    return res;
  }
}

复杂度分析

• 时间复杂度：O(NlogN)，N为节点个数。
• 空间复杂度：O(N)。

[honeymeng-hub]

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])))

[JudyZhou95]

代码

class Solution:
    def solve(self, root):
        q = [(root, 0)]

        d = {}

        while q:
            cur, pos = q.pop(0)

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

        sorted_d = sorted(d.items(), key=lambda x: x[0])
        res = [x[1] for x in sorted_d]

        return res

复杂度:

TC: O(NlogN) SC: O(N)

[z1ggy-o]

DFS

思路

如果我们给每个 node 以 (row, col) 标识位置， 题目的意思就是输出每个列的最上方的那个 node 的值。

DFS 的过程中，我们带入 row，col 信息，和相同 col 已有 node 做对比就可以了。

最后结果需要排序，CPP 中使用有序 container 可以避免自己做这个事儿。

代码

CPP

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
void dfs(Tree* root, int row, int col, map<int, pair<int, int>>& top_of_cols);
vector<int> solve(Tree* root) {
   // dfs
   // traverse with row, colomn information
   // since bfs goes from level 1 to level h, if this is the first time we met the column, this is the top
   // we need sorted ans => O(nlogn), using sorted containers (like std::map)
    map<int, pair<int, int>> top_of_cols;  // col, <row, val>
    queue<int> q;
    vector<int> ans;

    dfs(root, 0, 0, top_of_cols);

    for (const auto& [_, v]: top_of_cols)
        ans.push_back(v.second);

    return ans;
}

void dfs(Tree* root, int row, int col, map<int, pair<int, int>>& top_of_cols)
{
    if (root == nullptr)
        return;

    dfs(root->left, row+1, col-1, top_of_cols);
    dfs(root->right, row+1, col+1, top_of_cols);

    if (top_of_cols.find(col) == top_of_cols.end()) {
        top_of_cols[col] = pair(row, root->val);
    } else {
        auto& [prev_row, _] = top_of_cols[col];
        if (prev_row > row)
            top_of_cols[col] = pair(row, root->val);
    }
}

复杂度分析

• 时间：O(nlogn)，n 是 node 数量。对于每个 node 我们将其加入 map (RBTree) 的时候都要进行 re-balancing，耗费 O(logn)
• 空间：O(n)

BFS

思路

BFS 按层级向下遍历，所以每次遇见一个新的 col 的时候，该 node 一定在该 col 的 top 位置。

代码

CPP

/**
 * class Tree {
 *     public:
 *         int val;
 *         Tree *left;
 *         Tree *right;
 * };
 */
vector<int> solve(Tree* root) {
    // dfs
    // the first one node that we meet in a new col is the top
    map<int, int> top_of_cols;  // <col, val>; map will sort the result for us
    queue<pair<int, Tree*>> q;  // <col, val>
    vector<int> ans;

    // assume root is at (0, 0)
    q.push(pair(0, root));
    while (!q.empty()) {
        int len = q.size();
        for (int i = 0; i < len; i++) {
            const auto& [col, node] = q.front();
            q.pop();

            if (top_of_cols.find(col) == top_of_cols.end()) {
                top_of_cols[col] = node->val;
            }
            if (node->left) q.push(pair(col-1, node->left));
            if (node->right) q.push(pair(col+1, node->right));
        }
    }

    for (const auto& [_, v]: top_of_cols)
        ans.push_back(v);

    return ans;
}

复杂度同上。

[alongchong]

class Solution {

    public int[] solve(Tree root) {
        if (root == null) return new int[0];
        // key-idx, value-node.val
        Map<Integer, Integer> nodeMap = new HashMap<>();
        Queue<Object[]> nodeQueue = new LinkedList<>();
        nodeQueue.offer(new Object[]{root, 0});
        while (!nodeQueue.isEmpty()) {
            Object[] pair = nodeQueue.poll();
            Tree node = (Tree) pair[0];
            int idx = (int) pair[1];

            if (!nodeMap.containsKey(idx)) {
                nodeMap.put(idx, node.val);
            }

            if (node.left != null) {
                nodeQueue.offer(new Object[]{node.left, idx - 1});
            }

            if (node.right != null) {
                nodeQueue.offer(new Object[]{node.right, idx + 1});
            }
        }

        int[] keys = new int[nodeMap.size()];
        int idx = 0;
        for (int key : nodeMap.keySet()) {
            keys[idx++] = key;
        }
        Arrays.sort(keys);
        int[] res = new int[nodeMap.size()];
        idx = 0;
        for (int key : keys) {
            res[idx++] = nodeMap.get(key);
        }
        return res;
    }
}

[hdyhdy]

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
 }

type pair struct {
    node *TreeNode
    x int
}
var dict map[int]int

func bfs(root *TreeNode, dict map[int]int){
    q := []pair{}
    q = append(q,pair{root,0})
    for len(q) > 0{
        kvp := q[0]
        node := kvp.node
        x := kvp.x
        if _,ok := dict[x];!ok{
            dict[x] = node.Val
        }
        q = q[1:]
        if node.Left != nil{
            q = append(q,pair{node.Left,x-1})
        }
        if node.Right != nil{
            q = append(q,pair{node.Right,x+1})
        }
    }
}

func solve(root *TreeNode) []int{
    dict = map[int]int{}
    bfs(root,dict)
    out := []int{}
    min ,max := math.MaxInt32,math.MinInt32
    for x,_ := range dict{
        if x < min{
            min = x
        }
        if x > max{
            max = x
        }
    }
    for i:=min;i<=max;i++{
        out = append(out,dict[i])
    }
    return out
}

[Aobasyp]

思路 层次遍历简化纵坐标的判断 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])))

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

[stackvoid]

思路

BFS

代码

class Solution {
    public int[] solve(Tree root) {
        if (root == null) {
            return new int[0];
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        Queue<Tree> q = new LinkedList<>();
        Queue<Integer> index = new LinkedList<>();
        int min_id = 0;
        q.offer(root);
        index.offer(0);

        while (!q.isEmpty()) {
            Tree curr = q.poll();
            int id = index.poll();
            if (!map.containsKey(id)) {
                map.put(id, curr.val);
                min_id = Math.min(min_id, id);
            }

            if (curr.left != null) {
                q.offer(curr.left);
                index.offer(id - 1);
            }

            if (curr.right != null) {
                q.offer(curr.right);
                index.offer(id + 1);
            }
        }

        int n = map.size();
        int res[] = new int[n];
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            res[e.getKey() - min_id] = e.getValue();
        }

        return res;
    }
}

复杂度分析

Time O(N) Space O(1)

[testeducative]

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])))

[naomiwufzz]

思路：bfs

bfs看是最方便的，因为dfs的话就要记录更多结点的坐标了。bfs一层一层看，其实不需要完整的横纵坐标，横坐标即可，因为纵坐标不重要，可以用一个hash，只记录一次，下次再看到相同的横坐标就跳过。

代码

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def solve(self, root):
        # root是(0, 0)，0位置相同就不继续了
        if not root:
            return []
        q = deque([(root, 0)])
        h = {0: root.val}
        while q:
            for _ in range(len(q)):
                cur, hori = q.popleft()
                if cur.left:
                    q.append((cur.left, hori-1))
                    if hori-1 not in h:
                        h[hori-1] = cur.left.val
                if cur.right:
                    q.append((cur.right, hori+1))
                    if hori+1 not in h:
                        h[hori+1] = cur.right.val
        return [h[k] for k in sorted(h)]

复杂度分析

• 时间复杂度：O(nlogn) bfs是O(n)所有节点遍历一次，但因为后面需要排序，是nlogn
• 空间复杂度：O(n)

[guangsizhongbin]

import java.util.*;

/**

• public class Tree {
• int val;
• Tree left;
• Tree right;

• } */ class Solution {

  public int[] solve(Tree root) { Queue<Object[]> queue = new LinkedList<>(); SortedMap<Integer, Integer> map= new TreeMap(); queue.offer(new Object[]{root, 0}); map.put(0, root.val); while(!queue.isEmpty()) { Object[] o = queue.poll(); Tree node = (Tree)o[0]; int col = (int)o[1]; if(node.left != null) { queue.offer(new Object[]{node.left, col - 1}); if(!map.containsKey(col - 1)) { map.put(col - 1, node.left.val); }

      }
      if(node.right != null) {
          queue.offer(new Object[]{node.right, col + 1});
          if(!map.containsKey(col + 1)) {
              map.put(col + 1, node.right.val);
          }
      }
  }
  int [] res = new int[map.size()];
  int cnt = 0;
  for(int i : map.values()) res[cnt++] = i;
  return res;

  } }

[Serena9]

代码

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])))

[Toms-BigData]

ype TreeNode struct { Val int Left TreeNode Right TreeNode }

type pair struct { node *TreeNode x int } var dict map[int]int

func bfs(root *TreeNode, dict map[int]int){ q := []pair{} q = append(q,pair{root,0}) for len(q) > 0{ kvp := q[0] node := kvp.node x := kvp.x if _,ok := dict[x];!ok{ dict[x] = node.Val } q = q[1:] if node.Left != nil{ q = append(q,pair{node.Left,x-1}) } if node.Right != nil{ q = append(q,pair{node.Right,x+1}) } } }

func solve(root *TreeNode) []int{ dict = map[int]int{} bfs(root,dict) out := []int{} min ,max := math.MaxInt32,math.MinInt32 for x,_ := range dict{ if x < min{ min = x } if x > max{ max = x } } for i:=min;i<=max;i++{ out = append(out,dict[i]) } return out }

[GaoMinghao]

思路

虽然很慢，但是也是自己做出来的，开心，BFS层次遍历，用一个数组记录是否已经被记录过这个index的数字，由于是自上而下访问，因此可以判断

代码

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    class QueueNode {
        Tree tree;
        int index;

        QueueNode(Tree tree, int index) {
            this.tree = tree;
            this.index = index;
        }
    }
    public int[] solve(Tree root) {
        if(root == null)
            return new int[]{};
        long[] record = new long[20000];
        long initialNo = ((long) Integer.MIN_VALUE) - 1;
        Arrays.fill(record, initialNo);
        Queue<QueueNode> queue = new LinkedList<>();
        int index = 10000;
        QueueNode begin = new QueueNode(root, index);
        record[index] = root.val;
        queue.add(begin);
        while (!queue.isEmpty()) {
            QueueNode currentQueueNode = queue.poll();
            if(record[currentQueueNode.index] == initialNo) {
                record[currentQueueNode.index] = currentQueueNode.tree.val;
            }
            if(currentQueueNode.tree.left!=null) {
                QueueNode leftNode = new QueueNode(currentQueueNode.tree.left,
                        currentQueueNode.index - 1);
                queue.add(leftNode);
            }
            if(currentQueueNode.tree.right!=null) {
                QueueNode rightNode = new QueueNode(currentQueueNode.tree.right,
                        currentQueueNode.index+1);
                queue.add(rightNode);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for(long i : record) {
            if(i!=initialNo)
                ans.add((int) i);
        }
        int[] realans = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++) {
            realans[i] = ans.get(i);
        }
        return realans;
    }
}

复杂度

时间复杂度 O(N)

[Myleswork]

思路

记录节点的val和y，x作为key，若遇到相同x的节点，则取y较小的节点的val，最后return即可

代码

    /**
    * class Tree {
    *     public:
    *         int val;
    *         Tree *left;
    *         Tree *right;
    * };
    */

    void backtrack(Tree* root,int x,int y,vector<int>& res,map<int,int>& Y,map<int,int>& val){
        if(!root) return;
        if(val.find(x)==val.end()){   //如果没有当前列，就记录
            Y[x] = y;
            val[x] = root->val;
        }
        else{                         //如果有，就记录更靠上的节点
            if(Y[x]>y) val[x] = root->val;
        }
        backtrack(root->left,x-1,y+1,res,Y,val);
        backtrack(root->right,x+1,y+1,res,Y,val);
    }
    vector<int> solve(Tree* root) {
        vector<int> res;
        map<int,int> Y;
        map<int,int> val;   
        backtrack(root,0,0,res,Y,val);
        for(auto it=val.begin();it!=val.end();it++){
            res.push_back(it->second);
        }
        return res;
    }

复杂度分析

时间复杂度：O(n) n为节点的数量

空间复杂度：O(n)

[shamworld]

class Solution {
    solve(root) {
        if(!root) return [];
        let res = [root.val];
        let queue = [[root,0]];
        let map = new Set();
        map.add(0);
        while(queue.length){
            const [node,level] = queue.shift();
            if(!map.has(level)){
                if(level>0){
                    res.push(node.val);
                } else {
                    res.unshift(node.val);
                }
                map.add(level);
            }
            if (node.left) queue.push([node.left, level - 1])
            if (node.right) queue.push([node.right, level + 1])
        }

        return res;
    }
}

[LAGRANGIST]

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    class QueueNode {
        Tree tree;
        int index;

        QueueNode(Tree tree, int index) {
            this.tree = tree;
            this.index = index;
        }
    }
    public int[] solve(Tree root) {
        if(root == null)
            return new int[]{};
        long[] record = new long[20000];
        long initialNo = ((long) Integer.MIN_VALUE) - 1;
        Arrays.fill(record, initialNo);
        Queue<QueueNode> queue = new LinkedList<>();
        int index = 10000;
        QueueNode begin = new QueueNode(root, index);
        record[index] = root.val;
        queue.add(begin);
        while (!queue.isEmpty()) {
            QueueNode currentQueueNode = queue.poll();
            if(record[currentQueueNode.index] == initialNo) {
                record[currentQueueNode.index] = currentQueueNode.tree.val;
            }
            if(currentQueueNode.tree.left!=null) {
                QueueNode leftNode = new QueueNode(currentQueueNode.tree.left,
                        currentQueueNode.index - 1);
                queue.add(leftNode);
            }
            if(currentQueueNode.tree.right!=null) {
                QueueNode rightNode = new QueueNode(currentQueueNode.tree.right,
                        currentQueueNode.index+1);
                queue.add(rightNode);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for(long i : record) {
            if(i!=initialNo)
                ans.add((int) i);
        }
        int[] realans = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++) {
            realans[i] = ans.get(i);
        }
        return realans;
    }
}

[chakochako]

class Solution:
    def solve(self, root):
        q = deque([(root, 0)])
        x = {}
        while q:
            (node, xval) = q.popleft()
            if xval not in x:
                x[xval] = node.val
            if node.left:
                q.append((node.left, xval - 1))
            if node.right:
                q.append((node.right, xval + 1))
        return [j for (i, j) in sorted(list(x.items()))]

[machuangmr]

代码

class Solution {
     public int[] solve(Tree root) {
        if (root == null) {
            return new int[0];
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        Queue<Tree> q = new LinkedList<>();
        Queue<Integer> index = new LinkedList<>();
        int min_id = 0;
        q.offer(root);
        index.offer(0);

        while (!q.isEmpty()) {
            Tree curr = q.poll();
            int id = index.poll();
            if (!map.containsKey(id)) {
                map.put(id, curr.val);
                min_id = Math.min(min_id, id);
            }

            if (curr.left != null) {
                q.offer(curr.left);
                index.offer(id - 1);
            }

            if (curr.right != null) {
                q.offer(curr.right);
                index.offer(id + 1);
            }
        }

        int n = map.size();
        int res[] = new int[n];
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            res[e.getKey() - min_id] = e.getValue();
        }

        return res;
     }
}

[rzhao010]

Thoughts BFS + HashMap

**Code

public int[] solution(Tree root) {
    if (root == null) {
        return new int[0];
    }

    HashMap<Integer, Integer> map = new HashMap<>();
    Queue<Tree> q = new LinkedList<>();
    Queue<Integer> index = new LinkedList<>();
    int min_id = 0;
    q.offer(root);
    index.offer(0);

    while (!q.isEmpty()) {
        Tree cur = q.poll();
        int id = index.poll();
        if (!map.contains(id)) {
            map.put(id, cur.val);
            min_id = Math.min(min_id, id);
        }

        if (cur.left != null) {
            q.offer(cur.left);
            index.offer(id - 1);
        }

        if (cur.right != null) {
            q.offer(cur.right);
            index.offer(id + 1);
        }
    }
    int n = map.size();
    int res[] = new int[n];
    for (Map.Entry<Integer, Integer> e: map.entrySet()) {
        res[e.getKey() - min_id] = e.getValue();
    }
    return res;
}

Complexity Time: O(n) visited every tree node Space: O(n)

[Hacker90]

class Solution { solve(root) { if(!root) return []; let res = [root.val]; let queue = [[root,0]]; let map = new Set(); map.add(0); while(queue.length){ const [node,level] = queue.shift(); if(!map.has(level)){ if(level>0){ res.push(node.val); } else { res.unshift(node.val); } map.add(level); } if (node.left) queue.push([node.left, level - 1]) if (node.right) queue.push([node.right, level + 1]) }

    return res;
}

}

[wenlong201807]

代码块

class Node {
  constructor(data) {
    this.data = data;
    this.left = this.right = null;
    this.hd = 0;
  }
}

// Driver Code
function topview(root) {
  if (root == null) return;
  let q = [];
  let m = new Map();
  let hd = 0;
  root.hd = hd;
  q.push(root);

  while (q.length != 0) {
    root = q[0];
    hd = root.hd;
    if (!m.has(hd)) m.set(hd, root.data);
    if (root.left) {
      root.left.hd = hd - 1;
      q.push(root.left);
    }
    if (root.right) {
      root.right.hd = hd + 1;
      q.push(root.right);
    }
    q.shift();
  }

  let arr = Array.from(m);
  arr.sort(function (a, b) {
    return a[0] - b[0];
  });

  for (let [key, value] of arr.values()) {
    console.info(value + ' ');
  }
}

时间复杂度和空间复杂度

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