search

leetcode-pp / 91alg-6-daily-check

91 算法第六期打卡仓库
28 stars 0 forks source link

【Day 18 】2021-12-29 - 987. 二叉树的垂序遍历 #25

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

987. 二叉树的垂序遍历

入选理由

暂无

题目地址

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

前置知识

对位于 (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 之间。

yan0327 commented 2 years ago

思路： DFS + Sort自定义排序 + 扩展参数 首先用一个data结构体存储row、col、val，然后DFS搜索树前序遍历，将对应的row、col、val存储在data数据里面。 接着使用sort按照规则自定义排序。 最后一个for循环转换成二维数组。用一个pre表示前一个数的列数，一旦不一样另起一个维度用于插入数据。

type data struct{
    row,col,val int
}
func verticalTraversal(root *TreeNode) [][]int {
    out := [][]int{}
    if root == nil{
        return nil
    }
    ans := []data{}
    var dfs func(root *TreeNode,row ,col int)
    dfs = func(root *TreeNode,row,col int){
        if root == nil{
            return 
        }
        ans = append(ans, data{row:row,col:col,val:root.Val}) 
        dfs(root.Left,row+1,col-1)
        dfs(root.Right,row+1,col+1)
    }
    dfs(root,0,0)
    sort.Slice(ans, func(i,j int) bool{
        x,y := ans[i],ans[j]
        return x.col < y.col||(x.col==y.col&&x.row<y.row)||(x.col==y.col&&x.row==y.row&&x.val<y.val)
    })
    pre := math.MinInt32
    for i := range ans{
        if pre != ans[i].col{
            pre = ans[i].col
            out = append(out,[]int{})
        }
        out[len(out)-1] = append(out[len(out)-1],ans[i].val)
    }
    return out
}

时间复杂度O（NlogN） 空间复杂度O（N*M）

charlestang commented 2 years ago

思路

前序遍历，获得 col，row，val 的三元组序列。对序列排序后，格式化输出。

代码

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

        def dfs(root: TreeNode, row: int, col: int):
            if not root: return
            nodes.append((col, row, root.val))
            dfs(root.left, row + 1, col - 1)
            dfs(root.right, row + 1, col + 1)

        dfs(root,0,0)

        nodes = sorted(nodes)

        ans = []
        cols = []
        pre_c = nodes[0][0]
        for c, r, v in nodes:
            if c != pre_c:
                ans.append(cols)
                cols = [v]
                pre_c = c
            else:
                cols.append(v)
        if cols:
            ans.append(cols)
        return ans

时间复杂度 O(nlogn)

空间复杂度 O(n)

wxj783428795 commented 2 years ago

思路

  1. 前序遍历，以列号为key，将同一col的节点以[[row,val]]的形式，保存在散列表中
  2. 遍历散列表的值，以key从小到大排序。
  3. 排好序后的结果，即为从左到右的垂序遍历结果。
  4. 但是还要解决，同一列中，同一行的元素要从小到大排序的问题，因此需要再一次排序

代码

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
    let obj = {};
    let preOrder = function (node, row, col) {
        if (!node) return;
        if (obj[col]) {
            obj[col].push([row, node.val]);
        } else {
            obj[col] = [[row, node.val]];
        }
        preOrder(node.left, row + 1, col - 1);
        preOrder(node.right, row + 1, col + 1);
    }
    preOrder(root, 0, 0);//前序遍历，以列号为key，将同一col的节点以`[[row,val]]`的形式，保存在散列表中

    return Object.keys(obj).sort((a, b) => parseInt(a) - parseInt(b))//将列号从小到大排序
            .map(key => obj[key])
            .map(item=>{//如果同一列中有多个节点，接着排序
                if(item.length>0){
                    item = item.sort((a, b) => {//如果行号不同，则按行号从小到大排序
                        if (a[0] > b[0]) {
                            return 1
                        } else if (a[0] < b[0]) {
                            return -1
                        } else {//如果行号相同，则按照val从小到大排序
                            return a[1] - b[1]
                        }
                    })
                }
                return item
            })
            .map(item => item.map(item => item[1]))
};

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

feifan-bai commented 2 years ago

思路

  1. 从根节点对树遍历，nodes记录row, col和value

  2. 在遍历完成后，我们按照col, row, value排序 代码

    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)
Grendelta commented 2 years ago

思路

先进行dfs遍历每个节点，再把节点结果记录在dictionary里并进行排序

代码

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)

复杂度

时间复杂度O(NLOGN)

空间复杂度O(N)

wangzehan123 commented 2 years ago

代码

Java Code:


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);
        }
    }
}
CodeWithIris commented 2 years ago

Question

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

Note (DFS, Map, Pair)

Solution (C++)


class Solution {
public:
    void dfs(TreeNode* node, map<int, vector<pair<int, int>>>& mp, int row, int col){
        mp[col].emplace_back(row, node->val);
        if(node->left) dfs(node->left, mp, row + 1, col - 1);
        if(node->right) dfs(node->right, mp, row + 1, col + 1);
    }
    static bool cmp(pair<int ,int> a, pair<int,int> b){
        if(a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, vector<pair<int, int>>> mps; // column, <row, value>
        dfs(root, mps, 0, 0);
        vector<vector<int>> ans;
        for(auto& mp : mps){
            auto p = mp.second;
            sort(p.begin(), p.end(), cmp);
            vector<int> ele;
            for(auto& tmp : p){
                ele.push_back(tmp.second);
            }
            ans.push_back(ele);
        }
        return ans;
    }
};

Complexity

laofuWF commented 2 years ago 
# define a class represent a node with val, x, y
# in order traversal and store node in a dict, update min/max x 
# sort values of in each key-value pair in the dict by x then y then val
# iterate dict by key and add to res
# time: O(NlogN), for sorting
# space: O(N)

class Node:

    def __init__(self, val, x, y):
        self.val = val
        self.x = x
        self.y = y

class Solution:
    def __init__(self):
        self.min_order = float('inf')
        self.max_order = float('-inf')

    def comparator(self, node1, node2):
        if node1.x != node2.x:
            return node1.x - node2.x
        if node1.y != node2.y:
            return node1.y - node2.y
        return node1.val - node2.val

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        order_values = {}

        self.traverse(root, 0, 0, order_values);

        res = []
        temp_min = self.min_order

        for key in order_values:
            order_values[key].sort(key=cmp_to_key(self.comparator))

        while temp_min <= self.max_order:
            if not order_values.get(temp_min):
                continue
            curr_values = []
            for n in order_values.get(temp_min):
                curr_values.append(n.val)
            res.append(curr_values)

            temp_min += 1

        return res

    def traverse(self, node, x, y, order_values):
        if not node:
            return

        curr_list = order_values.get(x, [])
        new_node = Node(node.val, x, y)
        curr_list.append(new_node)
        order_values[x] = curr_list

        self.min_order = min(self.min_order, x)
        self.max_order = max(self.max_order, x)

        self.traverse(node.left, x - 1, y + 1, order_values)
        self.traverse(node.right, x + 1, y + 1, order_values)
tongxw commented 2 years ago

思路

先序dfs标记每个节点的(x,y)坐标，记录到哈希表里，最后根据(x, y)坐标排序，相同坐标的节点根据值排序，整理得出答案

代码

class Solution {
    TreeMap<Integer, TreeMap<Integer, List<Integer>>> map;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        map = new TreeMap<>(); // SC O(N)
        dfs(root, 0, 0); // TC O(N), SC O(logN)

        List<List<Integer>> ans = new ArrayList<>();
        for (int x : map.keySet()) { // TC O(X)
            List<Integer> list = new ArrayList<>();
            TreeMap<Integer, List<Integer>> levels = map.get(x);
            for (int y : levels.keySet()) { // TC O(Y)
                List<Integer> nodes = levels.get(y);
                Collections.sort(nodes); // TC O(K * logK)
                list.addAll(nodes);
            }

            ans.add(list);
        }

        return ans;
    }

    private void dfs(TreeNode root, int x, int y) {
        if (root == null) {
            return;
        }

        // TC O(X * LogX) + O(Y * LogY)
        map.computeIfAbsent(x, k -> new TreeMap<>()).computeIfAbsent(y, k -> new ArrayList<>()).add(root.val);
        dfs(root.left, x - 1, y + 1);
        dfs(root.right, x + 1, y + 1);
    }
}

SC: O(NLogN) 整体排序 TC: O(N) 哈希表

ZacheryCao commented 2 years ago

Idea

dfs. For each node, update its column and row, and append its value to the hash table. The hash table's key is the tuple of column and row. The value is the list of nodes' value we've visited at current column and row. For each column, we combine sorted list at different row, row by row. Then append it to the answer.

Code

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        memo = {}
        r_floor, r_ceil = 0, 0
        col = 0
        def dfs(root, c, r):
            nonlocal r_floor, r_ceil, col
            if not root:
                return
            if (c, r) in memo:
                memo[(c, r)].append(root.val)
            else:
                memo[(c, r)]=[root.val]
            col = max(col, r)
            r_floor = min(r_floor, c)
            r_ceil = max(r_ceil, c)
            dfs(root.left, c-1, r+1)
            dfs(root.right, c+1, r+1)
        ans = []
        dfs(root, 0, 0)
        for i in range(r_floor, r_ceil+1):
            ans.append([])
            for j in range(col+1):
                if (i, j) in memo:
                    ans[-1] += sorted(memo[(i, j)])
        return ans

Complexity

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

CoreJa commented 2 years ago

思路

代码

class Solution:
    # dfs+排序：用哈希表{col: list}的形式储存节点坐标，其中list的元素为tuple:(row,val)，以方便排序
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        d = defaultdict(list)

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

        dfs(root, 0, 0)
        return [[value[1] for value in sorted(x[1])] for x in sorted(list(d.items()))]
falconruo commented 2 years ago

思路: DFS

复杂度分析:

  1. 时间复杂度: O(n), n为树的节点数;
  2. 空间复杂度: O(n)

代码(C++):

/**
 * 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<vector<int>> verticalTraversal(TreeNode* root) {
        if (!root) return {};
        map<int, vector<pair<int, int>>> mp;
        vector<vector<int>> res;
        dfs(root, 0, 0, mp);

        for (auto it : mp) {
            vector<pair<int, int>> p = it.second;
            sort(p.begin(), p.end(), 
            [](const pair<int, int>& a, const pair<int, int>& b) { return (a.first < b.first || (a.first == b.first && a.second < b.second));
            });

            vector<int> tmp;
            for (auto t : p)
                tmp.push_back(t.second);
            res.push_back(tmp);
            tmp.clear();
            p.clear();
        }

        return res;
    }
private:
    void dfs(TreeNode* root, int x, int y, map<int, vector<pair<int, int>>>& mp) {
        if (!root) return;
        mp[x].push_back({y, root->val});
        dfs(root->left, x - 1, y + 1, mp);
        dfs(root->right, x + 1, y + 1, mp);
    }
};
zhangzz2015 commented 2 years ago

关键点

代码

C++ Code:


/**
 * 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<vector<int>> verticalTraversal(TreeNode* root) {

        map<int, map<int, multiset<int>>> record;

        dfs(root, 0, 0, record); 

        vector<vector<int>> ret(record.size());
        int count=0; 
        for(auto it = record.begin(); it!= record.end(); it++)
        {
            for(auto it2 = (*it).second.begin(); it2 !=(*it).second.end(); it2++)
            {
               for(auto it3 = (*it2).second.begin(); it3!=(*it2).second.end(); it3++) 
                  ret[count].push_back((*it3)); 
            }
            count++; 
        }
        return ret;
    }

    void dfs(TreeNode* root, int row, int col, map<int, map<int, multiset<int>>>& record)
    {
        if(root==NULL)
            return; 

        record[col][row].insert(root->val); 
        dfs(root->left, row+1, col-1, record); 
        dfs(root->right, row+1, col+1, record); 
    }
};
zwx0641 commented 2 years ago

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

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

}

YuyingLiu2021 commented 2 years ago

代码思路： 先用dfs遍历每一个node 得到横纵坐标和value的三元组 这里涉涉及到3个排序：col的排序，row的排序，node的value的排序 所以为了方便排序，在存储坐标时，col坐标在row坐标的前面 相同的列存到同一字典里，key为col，value为val

# 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]]:     
    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

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

ZhangNN2018 commented 2 years ago

思路

复杂度

代码

# 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 verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        def read(root, x, y): 
            if root:
                nums = d.get(x, [])
                nums.append((y, root.val)) #把层数y与结点val添加到第x列
                d[x] = nums
                read(root.left, x - 1, y + 1) #左列数-1，层数+1
                read(root.right, x + 1, y + 1) #右列数+1，层数+1

        d = dict() #key是列下标， value是这列各结点的(层数，值)的列表
        read(root, 0, 0) #遍历树

        res = list()
        for k in sorted(d.keys()): #列数排序，从左到右
            x = sorted(d[k])   #层数与值排序，从小到大
            x = [i[1] for i in x] #从(y, root.val)取val
            res.append(x)
        return res
zwmanman commented 2 years ago

思路

  1. dfs whole tree and append index(column and row) to a list
  2. sorted result and output each val in same column

代码

class Solution(object):
    def verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        vals = []
        res = []
        self.dfs(root, 0, 0, vals)
        last = -10000

        for x, y, val in sorted(vals):
            if x != last:
                res.append([])
                last = x
            res[-1].append(val)
        return res

    def dfs(self, root, x, y, vals):
        if root:
            vals.append((x, y, root.val))
            self.dfs(root.left, x - 1, y + 1, vals)
            self.dfs(root.right, x + 1, y + 1, vals)

复杂度分析

LannyX commented 2 years ago

思路

BFS + Hash Map

代码

class Solution {
    class Node{
        TreeNode root;
        int x;
        int y;
        Node(TreeNode root, int x, int y){
            this.root = root;
            this.x = x;
            this.y = y;
        }
    }
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Map<Integer, List<Node>> map = new HashMap<>();
        Queue<Node> q = new ArrayDeque<>();
        q.offer(new Node(root, 0,0));
        int minX = 0;
        int maxX = 0;
        while(!q.isEmpty()){
            Node cur = q.poll();
            //update min and max
            minX = Math.min(minX, cur.x);
            maxX = Math.max(maxX, cur.x);
            map.putIfAbsent(cur.x, new ArrayList<>());
            map.get(cur.x).add(cur);
            if(cur.root.left != null){
                q.offer(new Node(cur.root.left, cur.x - 1, cur.y - 1));
            }
            if(cur.root.right != null){
                q.offer(new Node(cur.root.right, cur.x + 1, cur.y - 1));
            }
        }
        int index = 0;
        for (int i = minX; i <= maxX; i++){
            Collections.sort(map.get(i), (a, b) ->{
                if(a.y == b.y){
                    return a.root.val - b.root.val;
                }
                return b.y - a.y;
            });
            res.add(new ArrayList<>());
            for(Node n : map.get(i)){
                res.get(index).add(n.root.val);
            }
            index++;
        }
        return res;
    }
}

复杂度分析

nonevsnull commented 2 years ago

思路

//s6

代码

//s6
class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        HashMap<Integer, HashMap<Integer, List<Integer>>> map = new HashMap<>();
        preOrder(root, map, 0, 0);
        int min = Collections.min(map.keySet()), max = Collections.max(map.keySet());
        for(int i = min;i <= max;i++){
            HashMap<Integer, List<Integer>> rows = map.get(i);
            int minRow = Collections.min(rows.keySet()), maxRow = Collections.max(rows.keySet());
            List<Integer> r = new ArrayList<>();

            for(int j = minRow;j <= maxRow;j++){
                if(rows.containsKey(j)){
                    List<Integer> vals = rows.get(j);
                    Collections.sort(vals);
                    r.addAll(vals);
                }

            }
            res.add(r);
        }

        return res;

    }

    public void preOrder(TreeNode root, HashMap<Integer, HashMap<Integer, List<Integer>>> map, int row, int col) {
        if(root == null) return;

        if(!map.containsKey(col)){
            HashMap<Integer, List<Integer>> rows = new HashMap<>();
            map.put(col, rows);
        }
        HashMap<Integer, List<Integer>> rows = map.get(col);
        if(!rows.containsKey(row)){
            List<Integer> vals = new ArrayList<>();
            rows.put(row, vals);
        }
        List<Integer> vals = rows.get(row);
        vals.add(root.val);

        preOrder(root.left, map, row + 1, col - 1);
        preOrder(root.right, map, row + 1, col + 1);
    }
}

复杂度

time: preorder需要遍历每个node，O(N);外部循环需要sort，理论上O(NlogN)；因此综合来说O(NlogN) space: 需要额外的空间存储map，O(N)

wenjialu commented 2 years ago

thought

Bfs or dfs Bfs: queue: update temp res into a defaultdict(list) rather than a list so that it can be easily sorted. In order to be correctly sorted that statisfied the requirement, should put col before row in to the temp_res. sorted the temp res, put the node with same col in one list.

code

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        # bfs, put its (row and col into a queue),
        # queue:(0,0) --> (1,-1)(1,1)
        #       (1,-1) --> (2,-2),(2,0)
        temp_res = collections.defaultdict(list)
        queue = collections.deque([(root, 0, 0 )])
        while queue:
            node, col, row = queue.popleft()
            temp_res[(col, row)].append(node.val)
            if node.left:
                queue.append((node.left, col - 1, row + 1))
            if node.right:
                queue.append((node.right, col + 1, row + 1))   

             last_col = float("-inf")
        res = []
        for col, row in sorted(temp_res.keys()):
            if col != last_col:
                last_col = col
                res.append(list())    
            res[-1].extend( sorted(temp_res[(col, row)])  )
        return res

        # dfs
    …

com

Time: O(nlogN) Space: O(n)

hdyhdy commented 2 years ago

思路： 首先构建一个结构体，其包括node以及col和row。利用BFS将node都存入一个切片。然后再对切片的内容进行排序，排序利用sort.slice函数。排序完以后再分别按照col分别输出。

type data struct{ col, row, val int }

func verticalTraversal(root *TreeNode) (ans [][]int) {
    nodes := []data{}
    var dfs func(*TreeNode, int, int)
    dfs = func(node *TreeNode, row, col int) {
        if node == nil {
            return
        }
        nodes = append(nodes, data{col, row, node.Val})
        dfs(node.Left, row+1, col-1)
        dfs(node.Right, row+1, col+1)
    }
    dfs(root, 0, 0)

    sort.Slice(nodes, func(i, j int) bool {
        a, b := nodes[i], nodes[j]
        return a.col < b.col || a.col == b.col && (a.row < b.row || a.row == b.row && a.val < b.val)
    })

    lastCol := math.MinInt32
    for _, node := range nodes {
        if node.col != lastCol {
            lastCol = node.col
            ans = append(ans, nil)
        }
        ans[len(ans)-1] = append(ans[len(ans)-1], node.val)
    }
    return
}

复杂度： 时间为nlogn，空间为n

CodingProgrammer commented 2 years ago

思路

遍历收集节点信息，然后再遍历收集的信息凑出答案

代码

class Solution {
    Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val
    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>> ans = 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]);
            ans.add(tmp);
            i = j;
        }
        return ans;
    }
    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);
        }
    }
}

复杂度

qihang-dai commented 2 years ago

DFS递归。HashMap 记录root -> int[]{col, row, val}. 没有java解法是真的牛逼.....

class Solution {
    HashMap<TreeNode, int[]> hash;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        hash = new HashMap<>();
        hash.put(root, new int[]{0, 0, root.val});
        dfs(root);
        List<int[]> map = new ArrayList<>(hash.values());
        Collections.sort(map, (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];
        });
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = 0; i < map.size(); ){//i不能递增，这玩的真花
            int j = i;
            List<Integer> tmp = new ArrayList<>();
            while(j < map.size() && map.get(j)[0] == map.get(i)[0]){
                tmp.add(map.get(j++)[2]);
            } 
            ans.add(tmp);
            i = j;
        }

        return ans;

    }

    public void dfs(TreeNode root){
        if(root == null) return;
        int[] tmp = hash.get(root);
        int col = tmp[0], row = tmp[1];
        if(root.left != null){
            hash.put(root.left, new int[]{col - 1, row + 1, root.left.val});
            dfs(root.left);
        }
        if(root.right != null){
            hash.put(root.right, new int[]{col + 1, row + 1, root.right.val});
            dfs(root.right);
        }

    }
}
Toms-BigData commented 2 years ago

【Day 18】987. 二叉树的垂序遍历

思路

新建一个结构体newNode，保存treenode的row,col,value,按照col,row,value的顺序进行排序，即col由小到大，row由小到大，value由小到大的顺序组成一个newNodeList。 遍历list,同一个value的保存在一个列表中，再存入ans中，输出ans

golang代码

type NewNode struct {
    Row int
    Col int
    Val int
}
type newnodeSlice []NewNode

func (s newnodeSlice) Len() int {return len(s)}
func (s newnodeSlice) Swap(i, j int) {s[i], s[j] = s[j], s[i]}
func (s newnodeSlice) Less(i, j int) bool {
    if s[i].Col<s[j].Col{
        return true
    }else if s[i].Col == s[j].Col{
        if s[i].Row <s[j].Row{
            return true
        }else if s[i].Row == s[j].Row{
            if s[i].Val < s[j].Val{
                return true
            }
        }
    }
    return false
}

func verticalTraversal(root *TreeNode) [][]int {
    if root==nil{
        return [][]int{}
    }
    newNodeList := newnodeSlice{}
    dfs(root, 0, 0, &newNodeList)
    sort.Sort(newNodeList)
    var ans [][]int
    minCol := newNodeList[0].Col-1
    for i:= 0;i<len(newNodeList);i++{
        if newNodeList[i].Col > minCol{
            newList := make([]int,0)
            newList = append(newList, newNodeList[i].Val)
            ans = append(ans, newList)
            minCol = newNodeList[i].Col
        }else{
            anslength:= len(ans)-1
            ans[anslength] = append(ans[anslength], newNodeList[i].Val)
        }
    }
    return ans
}
func dfs(node *TreeNode, row int, col int,newNodeList *newnodeSlice) {
    newNode := NewNode{row, col, node.Val}
    *newNodeList = append(*newNodeList, newNode)
    if node.Left!= nil{
        dfs(node.Left, row+1, col-1, newNodeList)
    }
    if node.Right!=nil{
        dfs(node.Right, row+1, col+1,newNodeList)
    }
}

复杂度

时间:O(NlogN) 空间:O(N)

watermelonDrip commented 2 years ago 
# 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]]:
        res_col = list()
        # levelOrder 
        def dfs(node,col,row):
            if not node:
                return
            res_col.append([col,row,node.val])
            dfs(node.left, col - 1 ,row +1)
            dfs(node.right,col + 1, row + 1)
        dfs(root,0,0)

        res_col.sort()
        tmp_col = inf
        res = list()
        for col,row, val in res_col:
            if tmp_col != col:
                tmp_col = col
                res.append([])

            res[-1].append(val)
        return (res)
suukii commented 2 years ago

Link to LeetCode Problem

S1: DFS 记录坐标+排序

把二叉树放到坐标网格上看看，以根节点为原点，往左的节点 x--，往右的节点 x++，往下的节点 y--。

https://camo.githubusercontent.com/36c0d85d07b7b9028cf20c19b87e242ea0e37216e9453e4bb5cfe0c965e48b1b/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f3938375f302e706e67

/**
 * 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<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> nodes;

        function<void(TreeNode* root, int x, int y)> dfs = [&](TreeNode* root, int x, int y) {
            if (root == nullptr) return;
            nodes.emplace_back(x, y, root->val);
            dfs(root->left, x - 1, y + 1);
            dfs(root->right, x + 1, y + 1);
        };

        dfs(root, 0, 0);
        sort(nodes.begin(), nodes.end());
        vector<vector<int>> ans;
        int curX = INT_MIN;
        for (const auto& [x, y, val] : nodes) {
            if (x > curX) {
                curX = x;
                ans.emplace_back();
            }
            ans.back().push_back(val);
        }
        return ans;
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
    if (!root) return [];

    // 坐标集合以 x 坐标分组
    const pos = {};
    // dfs 遍历节点并记录每个节点的坐标
    dfs(root, 0, 0);

    // 得到所有节点坐标后，先按 x 坐标升序排序
    let sorted = Object.keys(pos)
        .sort((a, b) => +a - +b)
        .map(key => pos[key]);

    // 再给 x 坐标相同的每组节点坐标分别排序
    sorted = sorted.map(g => {
        g.sort((a, b) => {
            // y 坐标相同的，按节点值升序排
            if (a[0] === b[0]) return a[1] - b[1];
            // 否则，按 y 坐标降序排
            else return b[0] - a[0];
        });
        // 把 y 坐标去掉，返回节点值
        return g.map(el => el[1]);
    });

    return sorted;

    // *********************************
    function dfs(root, x, y) {
        if (!root) return;

        x in pos || (pos[x] = []);
        // 保存坐标数据，格式是: [y, val]
        pos[x].push([y, root.val]);

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

S2: BFS 记录坐标+排序

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function (root) {
    if (!root) return [];

    // 坐标集合以 x 坐标分组
    const pos = bfs(root);

    // 得到所有节点坐标后，先按 x 坐标升序排序
    let sorted = Object.keys(pos)
        .sort((a, b) => +a - +b)
        .map(key => pos[key]);

    // 再给 x 坐标相同的每组节点坐标分别排序
    sorted = sorted.map(g => {
        g.sort((a, b) => {
            // y 坐标相同的，按节点值升序排
            if (a[0] === b[0]) return a[1] - b[1];
            // 否则，按 y 坐标降序排
            else return b[0] - a[0];
        });
        // 把 y 坐标去掉，返回节点值
        return g.map(el => el[1]);
    });

    return sorted;

    // *********************************
    function bfs(root) {
        // 队列中数据格式是: [x, y, val]
        const queue = [[0, 0, root]];
        const pos = {};
        while (queue.length) {
            let size = queue.length;

            while (size--) {
                const [x, y, node] = queue.shift();
                x in pos || (pos[x] = []);
                // 保存坐标数据到 pos，格式是: [y, val]
                pos[x].push([y, node.val]);
                node.left && queue.push([x - 1, y - 1, node.left]);
                node.right && queue.push([x + 1, y - 1, node.right]);
            }
        }
        return pos;
    }
};
ZZRebas commented 2 years ago

思路

DFS，获取每个节点的坐标，再按x坐标排序，再按y坐标排序，再按节点大小排序

代码(Python)

import collections
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

复杂度分析

iambigchen commented 2 years ago

思路

dfs遍历，用map记录每个x对应的节点和该节点对应的y值。遍历完成后，再进行排序

关键点

代码

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 null
    let map = {}
    function dfs (node, x, y) {
        if (node) {
            if (map[x]) {
                map[x].push([node.val, y])
            } else {
                map[x] = [[node.val, y]]
            }
            dfs(node.left, x-1, y-1)
            dfs(node.right, x+1, y-1)
        }
    }
    dfs(root, 0, 0)
    let keys = Object.keys(map).sort((a, b) => a-b)
    let res = keys.map(key => {
        return map[key].sort((a1, b1) => {
            if (a1[1] === b1[1]) {
                return a1[0] - b1[0]
            }
            return -a1[1] + b1[1]
        }).map((e) => {
            return e[0]
        })
    })
    return res
};

复杂度分析

令 n 为数组长度。

GaoMinghao commented 2 years ago

思路

BFS，先按col排序到treeMap中，再将每个value按先row，row相同看value 排序

代码

/**
 * 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 class Point {
        TreeNode treeNode;
        int row;
        int col;
        Point(TreeNode treeNode,int row, int col) {
            this.treeNode = treeNode;
            this.row = row;
            this.col = col;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<Point>> records = new TreeMap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        List<Point> pointList = new ArrayList<Point>();
        pointList.add(new Point(root,0,0));
        while (!pointList.isEmpty()) {
            Point point = pointList.get(0);
            if(records.get(point.col) == null) {
                List<Point> treeNodes = new ArrayList<>();
                treeNodes.add(point);
                records.put(point.col,treeNodes);
            }else {
                records.get(point.col).add(point);
            }
            if(point.treeNode.left!=null) {
                pointList.add(new Point(point.treeNode.left, point.row+1, point.col-1));
            }
            if(point.treeNode.right!=null) {
                pointList.add(new Point(point.treeNode.right,point.row+1,point.col+1));
            }
            pointList.remove(0);
        }
        List<List<Integer>> results = new ArrayList<>();
        for(Map.Entry<Integer, List<Point>> entry: records.entrySet()) {
            List<Point> points = entry.getValue();
            points.sort(new Comparator<Point>() {
                @Override
                public int compare(Point o1, Point o2) {
                    if(o1.row != o2.row) return o1.row - o2.row;
                    return o1.treeNode.val - o2.treeNode.val;
                }
            });
            List<Integer> result = new ArrayList<>();
            for(Point point:points) {
                result.add(point.treeNode.val);
            }
            results.add(result);
        }
        return results;
    }
}

复杂度

时间复杂度 O(n+n*nlogn) -> java 自带的sort函数使用的方法位timsort，其时间复杂度位O(n log n) 整体死慢

tangjy149 commented 2 years ago

思路

先用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:
    #define x first
    #define y second
    map<int, vector<pair<int, int>>> heap;
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        dfs(root, {0, 0});
        vector<vector<int>> res;
        for (auto& [key, value] : heap) {
            vector<int> col;
            sort(value.begin(), value.end());
            for (auto& each : value) {
                col.push_back(each.y);
            }
            res.push_back(col);
        }
        return res;
    }

    void dfs(TreeNode *root, pair<int, int> pos) {
        if (root == nullptr) return;
        heap[pos.y].emplace_back(pos.x, root->val);
        dfs(root->left, {pos.x + 1, pos.y - 1});
        dfs(root->right, {pos.x + 1, pos.y + 1});
    }
};
KennethAlgol commented 2 years ago

思路

DFS + Queue + 排序

语言

java

/**
 * 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 {
    PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->{ // col, row, val
        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];
    });
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        int[] info = new int[]{0, 0, root.val};
        queue.add(info);
        dfs(root, info);
        List<List<Integer>> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            int[] poll = queue.peek();
            while (!queue.isEmpty() && queue.peek()[0] == poll[0]){
                tmp.add(queue.poll()[2]);
            } 
            ans.add(tmp);
        }
        return ans;
    }
    public void dfs(TreeNode root, int[] fa) {
        if (root.left != null) {
            int[] linfo = new int[]{fa[0] - 1, fa[1] + 1, root.left.val};
            queue.add(linfo);
            dfs(root.left, linfo);
        }
        if (root.right != null) {
            int[] rinfo = new int[]{fa[0] + 1, fa[1] + 1, root.right.val};
            queue.add(rinfo);
            dfs(root.right, rinfo);
        }
    }
}

复杂度分析

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

guoling0019 commented 2 years ago

代码

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

复杂度分析

令 n 为数组长度。

ZJP1483469269 commented 2 years ago 
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        hashmap = dict()
        hashmap[root] =[0,0,root.val]
        dq = []
        dq.append(root)
        maxindex = 0
        minindex = 0
        while dq:
            node = dq.pop()
            index = hashmap[node][1]
            cro = hashmap[node][0]
            if node.left:
                dq.append(node.left)
                hashmap[node.left] = [cro + 1 ,index -1,node.left.val]
                minindex = min(index-1,minindex)
            if node.right:
                dq.append(node.right)
                hashmap[node.right] = [cro + 1 ,index +1,node.right.val]
                maxindex = max(maxindex,index + 1)
        res = []
        for _ in range(maxindex - minindex+1):
            res.append([])
        xx = hashmap.items()
        xx=sorted(xx,key = lambda x:(x[1][1],x[1][0],x[1][2]))

        for key,val in xx:
           res[val[1]-minindex].append(val[2]) 

        return res
samaritan1998 commented 2 years ago 
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
shamworld commented 2 years ago 
var verticalTraversal = function(root) {
    if(!root) return [];
    let map = {};
    deepTree(root,0,0);
    function deepTree(root,x,y){
        if(!root) return ;
         x in map || (map[x] = []);
         map[x].push([y,root.val]);
         deepTree(root.left,x-1,y-1);
         deepTree(root.right,x+1,y-1);
    }
    let sorted = Object.keys(map)
    .sort((a, b) => +a - +b)
    .map((key) => map[key]);

    // 再给 x 坐标相同的每组节点坐标分别排序
    sorted = sorted.map((g) => {
        g.sort((a, b) => {
        // y 坐标相同的，按节点值升序排
        if (a[0] === b[0]) return a[1] - b[1];
        // 否则，按 y 坐标降序排
        else return b[0] - a[0];
        });
        // 把 y 坐标去掉，返回节点值
        return g.map((el) => el[1]);
    });

    return sorted;

};
q815101630 commented 2 years ago

dfs+bfs 想法很朴素，首先dfs记录每个节点的垂序位置，然后bfs遍历树并把每个节点放入一个垂序位置：list[node]的哈希表。这里两两个注意的地方。

  1. 我们可以在dfs同时记录 最大和最小垂序位置，这样最后返回答案时候不需要给全局做排序。
  2. 使用一个临时哈希表把在dfs遍历中当前层所有垂序位置：list[node]记录，这样如果发现一个list[node] 长度大于1 时，我们就需要对其排序。
# 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]]:
        mini, maxi = float("inf"), float("-inf")
        def dfs(root, idx, nodeToIdx):
            nonlocal mini, maxi

            if not root:
                return

            nodeToIdx[root] = idx
            mini = min(mini, idx)
            maxi = max(maxi, idx)

            dfs(root.left,idx-1, nodeToIdx)
            dfs(root.right, idx+1, nodeToIdx)

        if not root:
            return []    

        nodeToIdx = {}
        dfs(root, 0, nodeToIdx)
        ret = collections.defaultdict(list)

        # bfs
        queue = collections.deque([root])            

        while queue:
            size = len(queue)
            curRow = collections.defaultdict(list)
            for _ in range(size):
                popped = queue.popleft()
                curRow[nodeToIdx[popped]].append(popped.val)

                if popped.left:
                    queue.append(popped.left)
                if popped.right:
                    queue.append(popped.right)

            # use a temporary variable to allows for the increasing order when same col, same row happens 
            for idx, lis in curRow.items():
                ret[idx].extend(sorted(lis))

        ans = []
        for i in range(int(mini), int(maxi+1)):
            ans.append(ret[i])
        return ans

时间: dfs: O(n) bfs: O(nlogn) 总 O(nlogn) 空间： O(n)

li65943930 commented 2 years ago

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

var verticalTraversal = function (root) { if (!root) return []; const pos = {}; dfs(root, 0, 0); let sorted = Object.keys(pos) .sort((a, b) => +a - +b) .map((key) => pos[key]); sorted = sorted.map((g) => { g.sort((a, b) => { if (a[0] === b[0]) return a[1] - b[1]; else return b[0] - a[0]; }); return g.map((el) => el[1]); });

return sorted;

// ***** function dfs(root, x, y) { if (!root) return;

x in pos || (pos[x] = []);
pos[x].push([y, root.val]);

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

} };

Tesla-1i commented 2 years ago 

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        memo = {}
        r_floor, r_ceil = 0, 0
        col = 0
        def dfs(root, c, r):
            nonlocal r_floor, r_ceil, col
            if not root:
                return
            if (c, r) in memo:
                memo[(c, r)].append(root.val)
            else:
                memo[(c, r)]=[root.val]
            col = max(col, r)
            r_floor = min(r_floor, c)
            r_ceil = max(r_ceil, c)
            dfs(root.left, c-1, r+1)
            dfs(root.right, c+1, r+1)
        ans = []
        dfs(root, 0, 0)
        for i in range(r_floor, r_ceil+1):
            ans.append([])
            for j in range(col+1):
                if (i, j) in memo:
                    ans[-1] += sorted(memo[(i, j)])
        return ans
Macvh commented 2 years ago

class Solution(object): def verticalTraversal(self, root): 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, lastcol = list[], float("-inf")

    for col, row, value in nodes:
        if col != lastcol:
            lastcol = col
            ans.append(list())
        ans[-1].append(value)

    return ans
xinhaoyi commented 2 years ago

987. 二叉树的垂序遍历

思路一

代码

 //用优先队列+dfs
class Solution {
    Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val
    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>> ans = 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]);
            ans.add(tmp);
            i = j;
        }
        return ans;
    }
    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);
        }
    }
}
Leonalhq commented 2 years ago

思路： dict+DFS，并且先对x再对y坐标排序， O(NlogN)

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        dic = defaultdict(list)
        self.helper(0,0, root, dic)
        result = []
        for i in sorted(dic.keys()):
            temp = []
            for j in sorted(dic[i]):
                temp.append(j[1])
            result.append(temp)
        return result
    def helper(self, placement,level, root, dic):
        if(not root):
            return
        dic[placement].append((level, root.val))
        self.helper(placement-1, level+1, root.left, dic)
        self.helper(placement+1, level+1, root.right, dic)
ginnydyy commented 2 years ago

Problem

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

Note

Solution

/**
 * 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 Node{
    TreeNode treeNode;
    int x;
    int y;
    public Node(TreeNode node, int x, int y){
        this.treeNode = node;
        this.x = x;
        this.y = y;
    }
}

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

        Map<Integer, List<Node>> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        Node rootNode = new Node(root, 0, 0);
        queue.offer(rootNode);
        List<Node> list = new ArrayList<>();
        list.add(rootNode);
        map.put(0, list);

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                Node cur = queue.poll();
                if(cur.treeNode.left != null){
                    int x = cur.x - 1;
                    int y = cur.y + 1;
                    Node leftNode = new Node(cur.treeNode.left, x, y);
                    queue.offer(leftNode);
                    if(map.get(x) == null){
                        List<Node> list1 = new ArrayList<>();
                        map.put(x, list1);
                    }
                    map.get(x).add(leftNode);
                }
                if(cur.treeNode.right != null){
                    int x = cur.x + 1;
                    int y = cur.y + 1;
                    Node rightNode = new Node(cur.treeNode.right, x, y);
                    queue.offer(rightNode);
                    if(map.get(x) == null){
                        List<Node> list2 = new ArrayList<>();
                        map.put(x, list2);
                    }
                    map.get(x).add(rightNode);
                }                
            }
        }

        List<Integer> keyList = new ArrayList<>(map.keySet());
        Collections.sort(keyList);

        for(int key: keyList){
            List<Node> nodeList = map.get(key);
            Collections.sort(nodeList,  (a, b) -> a.x == b.x && a.y == b.y? a.treeNode.val - b.treeNode.val: a.y - b.y);
            List<Integer> valueList = new ArrayList<>();
            for(Node node: nodeList){
                valueList.add(node.treeNode.val);
            }
            res.add(new ArrayList<>(valueList));
        }

        return res;
    }
}

Complexity

didiyang4759 commented 2 years ago

参考官方题解

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(n) 时间复杂度：O(n)

haixiaolu commented 2 years ago

思路

DFS + 排序， 排序是参考的code

代码 / Python


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

        groupby = collections.defaultdict(list)

        def dfs(node, x, y):
            groupby[x].append((y, node.val))
            if node.left:
                dfs(node.left, x -1, y + 1)
            if node.right:
                dfs(node.right, x + 1, y + 1)

        dfs(root, 0, 0)

        return [[t[1] for t in sorted(groupby[x])] for x in sorted(groupby)]

复杂度分析：

Brent-Liu commented 2 years ago

思路

从根节点开始，对整棵树进行一次遍历，在遍历的过程中使用数组 \textit{nodes}nodes 记录下每个节点的行号 \textit{row}row，列号 \textit{col}col 以及值 \textit{value}value。在遍历完成后，我们按照 \textit{col}col 为第一关键字升序，\textit{row}row 为第二关键字升序，\textit{value}value 为第三关键字升序，对所有的节点进行排序即可。

在排序完成后，我们还需要按照题目要求，将同一列的所有节点放入同一个数组中。因此，我们可以对 \textit{nodes}nodes 进行一次遍历，并在遍历的过程中记录上一个节点的列号 \textit{lastcol}lastcol。如果当前遍历到的节点的列号 \textit{col}col 与 \textit{lastcol}lastcol 相等，则将该节点放入与上一个节点相同的数组中，否则放入不同的数组中。

代码

class Solution { public List<List> 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> ans = new ArrayList<List>(); 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()); 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);
}

}

复杂度分析

biaohuazhou commented 2 years ago

思路

采用DFS方法 先序遍历整棵树 将每个节点的信息包括 row col values 记录到一个数组中，然后再将数组放到栈中 获取栈中记录的节点信息 按照列升序 再按照行升序 如果列和行都相同最后再按照值升序 最后再遍历这双层数组 列相同的放到同一个数组中 dfs 采用递归实现

代码

    class Solution {
        Map<TreeNode, int[]> map = new HashMap<TreeNode, int[]>();
        int col = 0, row = 0;

        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, new Comparator<int[]>() {
                @Override
                //按照列升序 再按照行升序 如果列和行都相同最后再按照值升序
                public int compare(int[] o1, int[] o2) {
                    if (o1[0] != o2[0]) {
                        return o1[0] - o2[0];
                    }
                    if (o1[1] != o2[1]) {
                        return o1[1] - o2[1];
                    }
                    return o1[2] - o2[2];
                }
            });
            //创建两层动态数组 最外层为每一列的数值  最里层为每一列中 重复出现的数值
            List<List<Integer>> ans = new ArrayList<>();
            int size = 0;
            //需要判断列是否相同，相同的列要放到一起
            int lastcol = Integer.MIN_VALUE;
            for (int[] node : list) {
                int col = node[0], row = node[1], value = node[2];
                if (col != lastcol) {
                    lastcol = col;
                    ans.add(new ArrayList<Integer>());
                    size++;
                }
                ans.get(size - 1).add(value);
            }
            return ans;

        }

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

    }

复杂度分析 时间复杂度： O(nlongn) n为节点数 dfs遍历需要O(n)时间 排序需要O(nlongn) 最后的遍历数组O(n) 所以总的时间为O(nlongn) 空间复杂度：O(n)为动态数组所需要的大小

zol013 commented 2 years ago 
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        colhash = defaultdict(list)
        queue = [(root, 0, 0)]
        mincol = maxcol = 0
        while queue:
            node, row, col = queue.pop(0)
            colhash[col].append((row, node.val))
            mincol = min(mincol, col)
            maxcol = max(maxcol, col)
            if node.left:
                queue.append((node.left, row + 1, col - 1))
            if node.right:
                queue.append((node.right, row + 1, col + 1))

        vertical = []
        for col in range(mincol, maxcol + 1):
            colhash[col].sort()
            vertical.append([val for row, val in colhash[col]])

        return vertical
Davont commented 2 years ago

code

var verticalTraversal = function(root) {
    let map = new Map()

    function dfs(root, row, col) {
        if (!root) return
        if (!map.has(col)) {
            map.set(col, new Map())
        }
        const item = map.get(col)
        if (!item.has(row)) {
            item.set(row, [])
        }
        item.get(row).push(root.val)
        dfs(root.left, row + 1, col - 1)
        dfs(root.right, row + 1, col + 1)
    }
    dfs(root, 0, 0)

    let arr = []
    for (let col of map) {
        arr.push(col)
    }

    return arr.sort((a, b) => a[0] - b[0]).map(item => {
        const arr = []
        for (let row of item[1]) {
            arr.push(row)
        }
        arr.sort((a, b) => a[0] - b[0])
        return arr.map(it => {
            if (it[1].length > 1) {
                it[1].sort((a, b) => a - b)
            }
            return it[1]
        }).flat()
    })
};
rzhao010 commented 2 years ago

Thoughts

  1. DFS the tree to save nodes to a map, value of each entry should be a new int[] contains col, row and val of each node
  2. Save value of map into a list, and sort it
  3. Traverse list, if the first element of array in the list is the same, then they are in the same col, save it to ans list

Code

class Solution {
    // key is node, value record col, row, val
    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>> ans = 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]);
            }
            ans.add(tmp);
            i = j;
        }        
        return ans;
    }

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

Complexity

pengfeichencpf commented 2 years ago

class Solution { public List<List> verticalTraversal(TreeNode root) { TreeMap<Integer, TreeMap<Integer, List>> map = new TreeMap<>(); dfs(root, 0, 0, map); List<List> allList = new ArrayList<>(); for(Map.Entry<Integer, TreeMap<Integer, List>> entry: map.entrySet()) { TreeMap<Integer, List> ymap = entry.getValue(); List list = new ArrayList<>(); for(Map.Entry<Integer, List> yentry: ymap.entrySet()) { // here it's order with y from small to big List items = yentry.getValue(); Collections.sort(items); list.addAll(0, items); } allList.add(list); } return allList; }

// map is x--> y-->list<val>
void dfs(TreeNode node, int x, int y, TreeMap<Integer, TreeMap<Integer, List<Integer>>> map) {
    if(null == node) return;
    TreeMap<Integer, List<Integer>> ymap = map.get(x);
    if(null == ymap) {
        ymap = new TreeMap<>();
        map.put(x, ymap);
    }
    List<Integer> list = ymap.get(y);
    if(null == list) {
        list = new ArrayList<>();
        ymap.put(y, list);
    }
    list.add(node.val);
    dfs(node.left, x-1, y-1, map); 
    dfs(node.right, x+1, y-1, map);
}

}