【Day 53 】2024-01-07 - 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

[Danielyan86]

class TreeNode:
    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None

def top_view(root):
    if not root:
        return []

    result = []
    queue = deque([(root, 0)])  # (node, horizontal_distance)
    horizontal_distance_map = defaultdict(list)

    while queue:
        node, hd = queue.popleft()

        if hd not in horizontal_distance_map:
            horizontal_distance_map[hd].append(node.val)

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

    # Sort the result based on horizontal distance
    sorted_hd = sorted(horizontal_distance_map.keys())
    for hd in sorted_hd:
        result.append(horizontal_distance_map[hd][0])

    return result

[Chloe-C11]

dic = {}
qu = deque([(root, 0)])
while qu:
    node, pos = qu.pop()
    if pos not in dic:
        dic[pos] = node.val

    if node.left:
        qu.appendleft((node.left, pos-1))

    if node.right:
        qu.appendleft((node.right, pos+1))

arr = list(dic.items())
arr.sort()

ans = []

for i in range(len(arr)):
    ans.append(arr[i][1])
return ans

Tc: O(N) SC: O(N)

[snmyj]

class Solution {
public:
    int findRadius(vector<int> &houses, vector<int> &heaters) {
        int ans = 0;
        sort(heaters.begin(), heaters.end());
        for (int house: houses) {
            int j = upper_bound(heaters.begin(), heaters.end(), house) - heaters.begin();
            int i = j - 1;
            int rightDistance = j >= heaters.size() ? INT_MAX : heaters[j] - house;
            int leftDistance = i < 0 ? INT_MAX : house - heaters[i];
            int curDistance = min(leftDistance, rightDistance);
            ans = max(ans, curDistance);
        }
        return ans;
    }
};

[joe-the-plumber]

打个卡

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

[larscheng]

思路

987. 二叉树的垂序遍历 Map+DFS

代码

class Solution {
     // key为横坐标x,value为[纵坐标y,节点值]的pair列表
    TreeMap<Integer, List<int[]>> map = new TreeMap<>();   

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        /*
        TreeMap+DFS:
        我们用TreeMap记录每个垂直列内的节点值,通过横坐标x与纵坐标y的DFS进行递归求解
         */
        dfs(root, 0, 0);
        List<List<Integer>> res = new ArrayList<>();
        // 排列后加入结果
        for (Integer idx : map.keySet()) {
            List<int[]> tmp = map.get(idx);
            tmp.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
            List<Integer> list = new ArrayList<>();
            for (int[] t : tmp) {
                list.add(t[1]);
            }
            res.add(list);
        }
        return res;
    }

    // 遍历root所在子树并将同一x内的节点信息加入map,其中x与y为root横纵坐标(前序遍历)
    private void dfs(TreeNode root, int x, int y) {
        // base case
        if (root == null) return;
        // 取出list进行插入并更新map
        List<int[]> list = map.getOrDefault(x, new ArrayList<>());
        list.add(new int[]{y, root.val});
        map.put(x, list);
        // 递归遍历左右子节点
        dfs(root.left, x - 1, y + 1);
        dfs(root.right, x + 1, y + 1);
    }
}

复杂度

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

[adfvcdxv]

高级

class Solution { public: int findRadius(vector &houses, vector &heaters) { int ans = 0; sort(heaters.begin(), heaters.end()); for (int house: houses) { int j = upper_bound(heaters.begin(), heaters.end(), house) - heaters.begin(); int i = j - 1; int rightDistance = j >= heaters.size() ? INT_MAX : heaters[j] - house; int leftDistance = i < 0 ? INT_MAX : house - heaters[i]; int curDistance = min(leftDistance, rightDistance); ans = max(ans, curDistance); } return ans; } };

[freeroo2]

代码

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

[Junru281]

其实整体思路不难, 我主要是卡壳在最后如何把HashMap放到res里面 参考: https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/solutions/906335/gong-shui-san-xie-yi-ti-shuang-jie-dfs-h-wfm3/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Map<TreeNode, int[]> m = new HashMap<>(); // treenode.val, row, col
        Queue<TreeNode> q = new LinkedList<>();

        m.put(root, new int[]{0, 0, root.val});
        q.add(root);

        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            if(cur.left != null){
                m.put(cur.left, new int[]{m.get(cur)[0] + 1, m.get(cur)[1]- 1, cur.left.val});
                q.add(cur.left);
            }

            if(cur.right != null){
                m.put(cur.right, new int[]{m.get(cur)[0] + 1, m.get(cur)[1] + 1, cur.right.val});
                q.add(cur.right);
            }

        }

        List<int[]> list = new ArrayList<>(m.values());
        Collections.sort(list, (a, b)->{
            if (a[1] != b[1]) return a[1] - b[1];
            if (a[0] != b[0]) return a[0] - b[0];
            return a[2] - b[2];
        });

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

时间复杂度: 令总节点数量为 n，填充哈希表时进行树的遍历，O(n)；写入res时需要排序，O(nlog⁡n)。整体复杂度为 O(nlog⁡n) 空间复杂度: O(n)