【Day 53 】2022-12-23 - 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

[bwspsu]

(Referring to solution)

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

[buer1121]

垂序遍历

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

定义一个哈希表，

    seen=collections.defaultdict(
        lambda:collections.defaultdict(list)
    )

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

    dfs(root)
    res=[]
    for y in sorted(seen):
        temp=[]
        for x in sorted(seen[y]):
            temp+= sorted(v for v in seen[y][x])

        res.append(temp)

    return res

[bookyue]

code

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> map = new TreeMap<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        Queue<Integer> queueOfCol = new ArrayDeque<>();
        queue.offer(root);
        queueOfCol.offer(0);

        int row = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                var cur = queue.poll();
                var col = queueOfCol.poll();
                assert col != null;

                map.computeIfAbsent(col, i -> new ArrayList<>()).add(new int[] {row, cur.val});

                if (cur.left != null) {
                    queue.offer(cur.left);
                    queueOfCol.offer(col - 1);
                }

                if (cur.right != null) {
                    queue.offer(cur.right);
                    queueOfCol.offer(col + 1);
                }
            }

            row++;
        }

        List<List<Integer>> ans = new ArrayList<>(map.size());
        map.values().forEach(list -> {
            list.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
            List<Integer> cur = new ArrayList<>();
            list.forEach(v -> cur.add(v[1]));

            ans.add(cur);
        });

        return ans;
    }

[FlipN9]

/**
    1. 遍历二叉树,对所有节点生成坐标
    2. 对所有节点排序
        - col: 从左到右
        - row: 从上到下
        - val: 从小到大
    3. 将排序好的节点组装成题目要求的格式

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

*/
// PQ
class Solution2 {
    record Info(TreeNode node, int col, int row) {}

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        PriorityQueue<Info> pq = new PriorityQueue<>((a, b) 
                                                     -> a.col != b.col? 
                                                        a.col - b.col : a.row != b.row? 
                                                        a.row - b.row : a.node.val - b.node.val);
        traverse(root, pq, 0, 0);
        while (!pq.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            Info cur = pq.poll();
            tmp.add(cur.node.val);
            int curCol = cur.col;
            while (!pq.isEmpty() && pq.peek().col == curCol) {
                tmp.add(pq.poll().node.val);
            }
            res.add(tmp);
        }
        return res;
    }

    private void traverse(TreeNode cur, PriorityQueue<Info> pq, int col, int row) {
        if (cur == null) return;
        pq.offer(new Info(cur, col, row));
        traverse(cur.left, pq, col - 1, row + 1);
        traverse(cur.right, pq, col + 1, row + 1);
    }
}

[chenming-cao]

解题思路

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

代码

/**
 * 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<>();
        if (root == null) return res;

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

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

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

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

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

复杂度分析

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

[zywang0]

class Solution {
    record Info(TreeNode node, int col, int row) {}

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        PriorityQueue<Info> pq = new PriorityQueue<>((a, b) 
                                                     -> a.col != b.col? 
                                                        a.col - b.col : a.row != b.row? 
                                                        a.row - b.row : a.node.val - b.node.val);
        traverse(root, pq, 0, 0);
        while (!pq.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            Info cur = pq.poll();
            tmp.add(cur.node.val);
            int curCol = cur.col;
            while (!pq.isEmpty() && pq.peek().col == curCol) {
                tmp.add(pq.poll().node.val);
            }
            res.add(tmp);
        }
        return res;
    }

    private void traverse(TreeNode cur, PriorityQueue<Info> pq, int col, int row) {
        if (cur == null) return;
        pq.offer(new Info(cur, col, row));
        traverse(cur.left, pq, col - 1, row + 1);
        traverse(cur.right, pq, col + 1, row + 1);
    }
}

[mayloveless]

思路

遍历节点，拿到坐标值，按横坐标排序，再按纵坐标排序，最后按值排序，然后遍历数组，按横坐标分组输出

代码

var verticalTraversal = function(root) {
    if (!root) return[];
    const orderNode = preorderTraversal(root);
    orderNode.sort((a,b) => {
        if (a.x !== b.x) {
            return a.x > b.x ? 1:-1 ;
        }
        if (a.y !== b.y) {
            return a.y > b.y ? 1:-1 
        }
        return a.val > b.val ? 1:-1
    });
    if (orderNode.length === 1) return [orderNode[0].val]

    let res = [];
    let left = 0;
    let right = 1;
    orderNode.push({
        val: -Infinity,
        x: Infinity,
        y: Infinity,
    })
    while(right < orderNode.length) {
        if (orderNode[left].x !== orderNode[right].x) {
            const arr = orderNode.slice(left, right).map(item => item.val);
            res.push(arr);
            left = right;
            continue
        }
        right++;
    }
    return res;
};

var preorderTraversal = function (root) {
    if (root == null) return [];
    const arr = [];
    arr.push({
        node: root,
        x:0,
        y:0,
    });
    const res = [];
    while (arr.length != 0) {
        var temp = arr.shift();
        res.push({
            val: temp.node.val,
            x: temp.x,
            y: temp.y,
        });
        if (temp.node.left) {
            arr.push({
                node: temp.node.left,
                x: temp.x-1,
                y: temp.y+1,
            });
        }
        if (temp.node.right) {
            arr.push({
                node: temp.node.right,
                x: temp.x+1,
                y: temp.y+1,
            });
        }
    }
    return res;
};

复杂度

时间 O(nlog(n))，排序需要O(nlogn) 空间 O(n）

[Jetery]

987. 二叉树的垂序遍历

思路

本题可以理解为以根节点为(0, 0), 向左为(x + 1, y - 1), 向右为(x + 1, y + 1)
y值越小(列越靠前), x越小(层考前)的先入列
使用 map + multiset, y权重大于x, 以y值映射键值对(x, val)
通过前序遍历整颗树

代码 (cpp)

class Solution {
public:

    typedef map<int, multiset<pair<int, int>>> MAP;

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

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        MAP mp;
        dfs(0, 0, root, mp);
        vector<vector<int>> ans;
        for (auto &[a, b] : mp) {
            vector<int> temp;
            for (auto &e : b) {
                temp.push_back(e.second);
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

复杂度分析

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

[tiandao043]

思路

dfs+排序

代码

/**
 * 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:
    typedef struct{
        int val;
        int r;
        int l;
    }treeno;

    static bool cmp(treeno a,treeno b)
    {
        if(a.l<b.l)return true;
        else if(a.l==b.l){
            if(a.r<b.r)return true;
            else if(a.r==b.r){
                return a.val<b.val;
            }
            else{
                return false;
            }
        }
        else{
            return false;
        }     
    }
    vector<treeno> temp;
    int dfs(TreeNode* root,int r,int l){
        if(root==nullptr)return 0;        
        else{
            treeno st;
            st.val=root->val;
            st.r=r;
            st.l=l;
            temp.push_back(st);
            dfs(root->left,r+1,l-1);
            dfs(root->right,r+1,l+1);
            return 1;
        }
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<vector<int>> ans;
        vector<int> t;       
        dfs(root,0,0);
        sort(temp.begin(),temp.end(),cmp);
        int index=temp.front().l;
        for(int i=0;i<temp.size();i++){
            if(index==temp[i].l){
                t.push_back(temp[i].val);
            }
            else{
                index=temp[i].l;
                ans.push_back(t);
                t.clear();
                i--;
            }
            // cout<<temp[i].val<<" ";
        }
        ans.push_back(t);
        return ans;
    }  
};

O(nlogn) O(n)

[klspta]

class Solution {
    public int finalValueAfterOperations(String[] operations) {
        int res = 0;
        for(String o : operations){
            char c = o.charAt(1);
            if(c == '-'){
                res--;
            }else if(c == '+'){
                res++;
            }
        }
        return res;
    }
}

[Abby-xu]

class Solution: def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]: g = collections.defaultdict(list) queue = [(root,0)] while queue: new = [] d = collections.defaultdict(list) for node, s in queue: d[s].append(node.val) if node.left: new += (node.left, s-1), if node.right: new += (node.right,s+1),
for i in d: g[i].extend(sorted(d[i])) queue = new return [g[i] for i in sorted(g)]

[klspta]

打不开，做了 Cl 的987 题

/**
 * 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 {

    private 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];
            }else if(a[1] != b[1]){
                return a[1] - b[1];
            }else{
                return a[2] - b[2];
            }
        });
        List<List<Integer>> ans = new ArrayList<>();
        int n = list.size();
        for(int i = 0; i < n;){
            List<Integer> col = new ArrayList<>();
            int j = i;
            while(j < n && list.get(i)[0] == list.get(j)[0]){
                col.add(list.get(j++)[2]);
            }
            ans.add(col);
            i = j;
        }
        return ans;
    }

    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        int[] xyz = map.get(root);
        int col = xyz[0];
        int row = xyz[1];
        int val = xyz[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);
        }
    }
}

[BruceZhang-utf-8]

思路 使用dfs遍历树 注意遍历过程中将树加入到map中，map的key为TreeNode,value为列，行和节点值 按照这三个排序，列从小到大，行从小到大，同行同列从小到大 关键点 代码 语言支持：Java Java Code:

/**

• 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 { Map<TreeNode,int[]> map=new HashMap<>(); public List<List> verticalTraversal(TreeNode root) { map.put(root,new int[]{0,0,root.val}); dfs(root); //对map中的节点进行排序，按照列号从小到大，行号从小到大，同行同列按值排序 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> ans = new ArrayList<>(); for (int i = 0; i < n;) { int j=i; List tmp = new ArrayList<>(); while(j<n && list.get(j)[0]==list.get(i)[0]){ tmp.add(list.get(j++)[2]);

      }
      ans.add(tmp);
      i=j;
  
  }
  return ans;

  }

  void dfs(TreeNode root){ if(root==null) return; int[] info=map.get(root); int col=info[0]; int row=info[1]; int 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); } } }

[RestlessBreeze]

二叉树的垂序遍历

代码

class Solution {
public:

    struct node
    {
        int val;
        int x;
        int y;
        node(int _val, int _x, int _y) : val(_val), x(_x), y(_y) {}
    };

    vector <node*> array;

    void DFS(TreeNode* root, int x, int y)
    {
        if (root)
        {
            node* temp = new node(root -> val, x, y);
            array.push_back(temp);
            DFS(root -> left, x - 1, y + 1);
            DFS(root -> right, x + 1, y + 1);
        }
    }

    static bool cmp(node* a, node* b)
    {
        if (a -> x != b -> x) return a -> x < b -> x;
        if (a -> y != b -> y) return a -> y < b -> y;
        return a -> val < b -> val;
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        DFS(root, 0, 0);
        sort(array.begin(), array.end(), cmp);
        int localx = -1000;
        vector<vector<int>> res;
        for (auto& s : array)
        {
            if (s -> x != localx)
            {
                res.emplace_back();
                localx = s -> x;
            }
            res.back().push_back(s -> val);
        }
        return res;
    }
};

[snmyj]

public void preOrderTraverse2(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pNode = root;
        while (pNode != null || !stack.isEmpty()) {
            if (pNode != null) {
                System.out.print(pNode.val+"  ");
                stack.push(pNode);
                pNode = pNode.left;
            } else { //pNode == null && !stack.isEmpty()
                TreeNode node = stack.pop();
                pNode = node.right;
            }
        }
    }

[xuanaxuan]

DFS

思路 先存着，再根据y,x，val做排序 代码

 var verticalTraversal = function (root) {
  const res = new Map([[0, [[root.val]]]])
  proder(root.left, 1, -1)
  proder(root.right, 1, 1)

  function proder(node, row, col) {
    if(!node) return;
      const arr = res.get(col) || []
      arr[row] = [...(arr[row] || []), node.val]
      res.set(col, arr)
      node.left && proder(node.left, row + 1, col - 1)
      node.right && proder(node.right, row + 1, col + 1)
  }
  const newLocal = [...res].sort(([a], [b]) => (a - b));
  const result = newLocal.reduce(function (total, [cur, arr]) {
      const items = arr.map(item => item.sort((a, b) => a - b)).flat()
      total.push(items)
      return total;
  }, [])
  return result;
};

复杂度

• 时间复杂度：O(NlogN)，其中 N 为树的节点总数。
• 空间复杂度：O(N)，其中 N 为树的节点总数。

[MaylingLin]

[91-53]Top-View-of-a-Tree

思路

---

BFS层次遍历

代码

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

复杂度

---

• Time: $O(nlogn)$，令n节点数。
• Space: $O(n)$

[paopaohua]

class Solution {
      // x {y : [val,val,...]}
    Map<TreeNode,int[]> map = new  HashMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
    map.put(root, new int[]{0,0,root.val}); // root的位置为（0,0,val）
       // 坐标集合以 x 坐标分组
     // dfs 遍历节点并记录每个节点的坐标
    dfs(root);
    List<int[]> list = new ArrayList<>(map.values());
  // 得到所有节点坐标后，先按 x 坐标升序排序
    // 再给 x 坐标相同的每组节点坐标分别排序
    // y 坐标相同的，按节点值升序排
      // 否则，按 y 坐标降序排
    Collections.sort(list,(a,b)->{  // lamda表达式定义排序规则
        if(a[0] != b[0]) return a[0] - b[0];
        if(a[1] != b[1]) return a[1] - b[1];
        return a[2] - b[2];
    });
    int n = list.size();
    List<List<Integer>> ans = new ArrayList<>();
    // 将list中的值放到ans中
     for (int i = 0; i < n; ) {
            int j = i;
            List<Integer> tmp = new ArrayList<>();
            while (j < n && list.get(j)[0] == list.get(i)[0]) 
                tmp.add(list.get(j++)[2]);
            ans.add(tmp);
            i = j;
        }
    return ans;
    }
    public void dfs(TreeNode root){
        if(root == null) return;
        int[] arr = map.get(root);
        //初始化 x ，y
        int x = arr[0];
        int y =  arr[1];
        int val = arr[2];
        if(root.left != null){
            // 坐标迭代
            map.put(root.left,new  int[]{x - 1,y + 1,root.left.val});
            dfs(root.left);
        }
         if(root.right != null){
            map.put(root.right,new int[]{x + 1,y + 1,root.right.val});
            dfs(root.right);
        }
    }
}

[Ryanbaiyansong]

# 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]]:
        # 二叉树的竖直遍历, 竖直遍历: 大方向是从左到右, 小方向是从上到下
        # 先存储大方向, 再存储小方向, 大方向是colIndex, 小方向是rowIndex
        q = deque([(0, 0, root)])
        pos = defaultdict(list)
        while q:
            r, c, node = q.popleft()
            pos[c].append((r, node.val))
            if node.left:
                q.append((r+1, c-1, node.left))
            if node.right:
                q.append((r+1, c+1, node.right))

        res = []
        cols = sorted(pos.keys())
        for c in cols:
            nodes = sorted(pos[c])
            cur = []
            for _, val in nodes:
                cur.append(val)
            res.append(cur)
        return res