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

5 stars 0 forks source link

【Day 18 】2022-08-01 - 987. 二叉树的垂序遍历 #33

Closed azl397985856 closed 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 之间。

andyyxw commented 2 years ago

/*
 * Algorithm: BFS
 * Time Complexity: O(nlogn)
 * Space Complexity: O(n)
 */
function verticalTraversal(root: TreeNode | null): number[][] {
  if (!root) return []

  const queue: [[number, TreeNode]] = [[0, root]]
  const map = new Map([[0, [root.val]]])
  while (queue.length) {
    let len = queue.length
    const tempMap = new Map<number, number[]>()
    while (len--) {
      const [x, root] = queue.shift()
      if (root.left) {
        queue.push([x - 1, root.left]);
        tempMap.set(x - 1, (tempMap.get(x - 1) || []).concat(root.left.val))
      }
      if (root.right) {
        queue.push([x + 1, root.right]);
        tempMap.set(x + 1, (tempMap.get(x + 1) || []).concat(root.right.val))
      }
    }
    tempMap.forEach((value, key) => {
      value.sort((a, b) => a - b)
      map.set(key, (map.get(key) || []).concat(value))
    })
  }
  return [...map.keys()].sort((a, b) => a - b).map(v => map.get(v))
}

laofuWF commented 2 years ago

# 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

# x > y > val
# time: O(N + hlogh), space: O(N)
class Solution:
    def __init__(self):
        self.min_x = float('inf')
        self.max_x = float('-inf')

    def comparator(self, node1, node2):
        # [y, val]
        if node1[0] != node2[0]:
            return node1[0] - node2[0]
        return node1[1] - node2[1]

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        x_cord = {} # x: [y, val]
        self.traverse(root, x_cord, 0, 0)
        res = []

        for i in range(self.min_x, self.max_x + 1):
            if i in x_cord:
                curr_list = []
                x_cord[i].sort(key=cmp_to_key(self.comparator))
                for n in x_cord[i]:
                    curr_list.append(n[1])
                res.append(curr_list.copy())

        return res

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

        self.min_x = min(self.min_x, x)
        self.max_x = max(self.max_x, x)

        if x not in x_cord:
            x_cord[x] = []
        x_cord[x].append([y, node.val])

        self.traverse(node.left, x_cord, x - 1, y + 1)
        self.traverse(node.right, x_cord, x + 1, y + 1)

joeymoso commented 2 years ago

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        # dictionary to store the coordinates of nodes 
        dic=collections.defaultdict(list)
        # node, col, row
        queue = collections.deque([[root, 0, 0]])

        # bfs
        while queue:
            node, c, r = queue.popleft()
            dic[(c, r)].append(node.val)
            if node.left:
                queue.append([node.left, c - 1, r + 1])
            if node.right:
                queue.append([node.right, c + 1, r + 1])

         # sort
        ans, temp = [], []
        currentCol = None
        for j, i in sorted(dic.keys()):
            if j != currentCol:
                ans.append(temp)
                temp = []
                currentCol = j
            temp.extend(sorted(dic[(j, i)]))
        ans.append(temp)
        return ans[1:]

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

flaming-cl commented 2 years ago

/**
 * 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[][]}
 */

// T: O(col * log(Max Row))
// S: O(N) 
const verticalTraversal = function(root) {
    if (!root.left && !root.right) return [[root.val]];
    const hash = {};
    dfs(root, 0, 0, hash);
    const res = [];
    Object.keys(hash).sort((a, b) => a - b).forEach(col => {
        res.push(hash[col].sort(sortCol).map(node => node[2]));
    })
    return res;
};

const sortCol = (a, b) => {
    if (a[0] !== b[0]) {
        return a[0] - b[0];
    }
    if (a[1] !== b[1]) {
        return a[1] - b[1];
    }
    if (a[2] != b[2]) {
        return a[2] - b[2];
    }
}

const dfs = (root, row, col, hash) => {
    if (root == null) return;
    if (hash[col] === undefined) {
        hash[col] = [];
    }
    hash[col].push([col, row, root.val]);
    dfs(root.left, row + 1, col - 1, hash);
    dfs(root.right, row + 1, col + 1, hash);
}

MichaelXi3 commented 2 years ago

Idea

DFS traversal, then input res by columns

Code


class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
// Marking each node with coordinates for verticalTraversal
// Param: (KEY) column in ascending, (Val) TreeMap<Row in ascending, Node Val in ascending>
TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();
dfs(map, root, 0, 0);

    // Printout res in Column order
    List<List<Integer>> res = new ArrayList<>();
    for (TreeMap<Integer, PriorityQueue<Integer>> col : map.values()) {
        List<Integer> curColumn = new ArrayList<>();
        for (PriorityQueue<Integer> row : col.values()) {
            while (!row.isEmpty()) {
                curColumn.add(row.poll());
            }
        }
        res.add(new ArrayList<>(curColumn));
    }
    return res;
}

public void dfs(TreeMap<Integer,TreeMap<Integer, PriorityQueue<Integer>>> map, TreeNode root, int x, int y) {
    // Base case
    if (root == null) { return;}
    // If column visited
    if (map.containsKey(y)) {
        // If row visited
        if (map.get(y).containsKey(x)) {
            map.get(y).get(x).offer(root.val);
        } else {
            // Column visited, row didn't visit
            TreeMap<Integer, PriorityQueue<Integer>> rows = map.get(y);
            rows.put(x, new PriorityQueue<>());
            rows.get(x).offer(root.val);
        }
    } else {
        // Column didn't visit
        TreeMap<Integer, PriorityQueue<Integer>> row = new TreeMap<>();
        row.put(x, new PriorityQueue<>());
        row.get(x).offer(root.val);
        map.put(y, row);
    }
    // Keep DFS
    dfs(map, root.left, x + 1, y - 1);
    dfs(map, root.right, x + 1, y + 1);
}

}

yopming commented 2 years ago

思路

中心思想还是DFS，遍历的时候把x y 和 val都记录在stack中，方便最后的比较。所以这里构建了一个struct来记录x y 与 val，同时还有一个sort的方法，先比较x，再比较y，最后才是val如果两个节点的x和y都相等的话。

使用一个hashmap来按照y也就是vertical order作为hash存储node的vector（应用自定义sort方法的地方），也就是所有vertical order为0的在一个vector中，vectical order为1的在一个vector中，以此类推。

同时，hashmap中不能保证key是sorted的，可以根据题目的给出的节点数量限制[0-1000]来做一个大的hashmap，但更通用的做法是把vertical order保存在一个set中，这样就可以从set中一个一个拿vertical order，然后用这个vertical order从hashmap中取node的vector（排序过的），然后生成二维vector返回。

代码

class Solution {
public:
  struct Node {
    int x;
    int y;
    int val;
    
    Node(int x_, int y_, int val_): x(x_), y(y_), val(val_) {}
  };
  
  // sort by row, column, value
  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) {
    std::vector<std::vector<int>> results;
    if (root == nullptr) return results;

    Node node_root = {0, 0, root->val};
    
    std::set<int> orders;
    std::unordered_map<int, std::vector<Node>> map;
    std::stack<std::pair<TreeNode*, Node>> stk;
    
    stk.emplace(root, node_root);
    while (!stk.empty()) {
      auto top = stk.top();
      stk.pop();
      
      TreeNode* top_node = top.first;
      int order_x = top.second.x;
      int order_y = top.second.y;
      map[order_y].push_back(top.second);
      if (orders.count(order_y) == 0) {
        orders.insert(order_y);
      }
      
      if (top_node->left) {
        Node left = {order_x + 1, order_y - 1, top_node->left->val};
        stk.emplace(top_node->left, left);
      }
      if (top_node->right) {
        Node right = {order_x + 1, order_y + 1, top_node->right->val};
        stk.emplace(top_node->right, right);
      }
    }

    for (auto order: orders) {
      std::vector<Node> nodes = map[order];
      std::sort(nodes.begin(), nodes.end(), cmp);
      std::vector<int> result;
      for (auto node: nodes) {
        result.push_back(node.val);
      }
      results.push_back(result);
    }

    return results;
  }
};

复杂度分析

时间复杂度 O(n logn). log n是排序的时间复杂度，因为排序在for循环中，循环最大数量是 n，也就是节点数量。虽然有第二层for循环，但这两层最多也就是遍历n次，所以仍然是O(n logn)
空间复杂度 O(n). 不论是set还是hashmap还是stack，最大长度均为n

haoyangxie commented 2 years ago

DFS

class Solution {
    class Node {
        int val;
        int row;

        public Node(int val, int row) {
            this.val = val;
            this.row = row;
        }
    }

    Map<Integer, List<Node>> map = new HashMap<>();
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);

        List<List<Integer>> res = new LinkedList<>();
        for (int i = min; i <= max; i++) {
            List<Node> temp = map.get(i);
            Collections.sort(temp, (a, b) -> {
                if (a.row == b.row) {
                    return a.val - b.val;
                } else {
                    return a.row - b.row;
                }
            });
            List<Integer> values = new ArrayList<>();
            for (Node n : temp) {
                values.add(n.val);
            }
            res.add(values);
        }
        return res;
    }

    private void dfs(TreeNode node, int col, int row) {
        if (node == null) {
            return;
        }
        min = Math.min(col, min);
        max = Math.max(col, max);

        List<Node> list = map.getOrDefault(col, new ArrayList<>());
        list.add(new Node(node.val, row));
        map.put(col, list);

        dfs(node.left, col - 1, row + 1);
        dfs(node.right, col + 1, row + 1);
    }
}

BFS

class Solution {
    class Group {
        TreeNode node;
        int row;
        int col;

        Group(TreeNode node, int row, int col) {
            this.node = node;
            this.row = row;
            this.col = col;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        HashMap<Integer, List<Group>> colMap = new HashMap<>();
        int minCol = Integer.MAX_VALUE;
        int maxCol = Integer.MIN_VALUE;

        Queue<Group> queue = new LinkedList<>();
        queue.add(new Group(root, 0, 0));

        while (!queue.isEmpty()) {
            Group node = queue.poll();

            int row = node.row;
            int col = node.col;

            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col);

            if (node.node.left != null) {
                queue.add(new Group(node.node.left, row + 1, col - 1));
            }
            if (node.node.right != null) {
                queue.add(new Group(node.node.right, row + 1, col + 1));
            }

            if (colMap.containsKey(node.col)) {
                colMap.get(node.col).add(node);
            } else {
                List<Group> list = new ArrayList<>();
                list.add(node);
                colMap.put(node.col, list);
            }
        }

        for (int i = minCol; i <= maxCol; i++) {
            List<Group> list = colMap.get(i);
            Collections.sort(list, (a, b) -> {
                if (a.row == b.row) {
                    return a.node.val - b.node.val;
                } else {
                    return a.row - b.row;
                }
            });

            List<Integer> values = new ArrayList<>();
            for (Group g : list) {
                values.add(g.node.val);
            }
            res.add(values);
        }
        return res;
    }
}

Complexity

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

richypang commented 2 years ago

思路

参考官方题解

代码

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        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 = []
        for x in sorted(seen):
            level = []
            for y in sorted(seen[x]):
                level += sorted(v for v in seen[x][y])
            ans.append(level)
        return ans

复杂度

时间复杂度: O(n^2)

空间复杂度:O(n)

herbertpan commented 2 years ago

Algo

 [1,2,3,4,6,5,7]
    |

  H V.  N
 <0,0, [1]>
 <1,-1,[2]>
 <2,-2,[4]>
 <2, 0,[6]>
 <1,1, [3]>
 <2, 0,[5]>
 <2,2, [7]>

group by vertical level, map<V, List<TUPLE>>   
tracking the loest vertivcal level -2

0: [<0,0, [1]>,  <2, 0,[6]>, <2, 0,[5]>]
-1:[<1,-1,[2]>]
-2:[<2,-2,[4]>]
1: [ <1,1, [3]>]
2: [<2,2, [7]>]

sort the list by horizontal level, then sort by value

convert to required type

Code

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

        // inorder traverse to collect nodes info as tuple<H,V, Node>
        List<NodeInfo> nodes = new ArrayList<>();
        inOrderTraverse(root, 0, 0, nodes);

        // group tuples by V => map<V, list<Tuple>> and track lowest vLEVEL;
        int lowestvLevel = 0;
        Map<Integer, List<NodeInfo>> vLevelToNodes = new HashMap<>();
        for (NodeInfo nodeInfo : nodes) {
            if (!vLevelToNodes.containsKey(nodeInfo.vLevel)) {
                vLevelToNodes.put(nodeInfo.vLevel, new ArrayList<>());
            }
            vLevelToNodes.get(nodeInfo.vLevel).add(nodeInfo);
            lowestvLevel = Math.min(lowestvLevel, nodeInfo.vLevel);
        }        

        // sort each entry's value, by H value and then node val
        for (Map.Entry<Integer, List<NodeInfo>> entry : vLevelToNodes.entrySet()) {
            Collections.sort(entry.getValue(), (a, b) -> {
                if (a.hLevel == b.hLevel) {
                    return a.node.val - b.node.val;
                } 
                return a.hLevel - b.hLevel;
            });
        }

        // convert to the answer
        while (vLevelToNodes.containsKey(lowestvLevel)) {
            List<NodeInfo> vlevelNodes = vLevelToNodes.get(lowestvLevel);
            List<Integer> vLevelAns = new ArrayList<>();
            for (NodeInfo nodeInfo : vlevelNodes) {
                vLevelAns.add(nodeInfo.node.val);
            }
            ans.add(vLevelAns);
            lowestvLevel++;
        }

        return ans;
    }

    private void inOrderTraverse(TreeNode node, int hLevel, int vLevel, List<NodeInfo> nodes) {
        if (node == null) {
            return;
        }        

        nodes.add(new NodeInfo(hLevel, vLevel, node));
        inOrderTraverse(node.left, hLevel + 1, vLevel - 1, nodes);
        inOrderTraverse(node.right, hLevel + 1, vLevel + 1, nodes);
    }

    private class NodeInfo {
        int hLevel;
        int vLevel;
        TreeNode node;

        public NodeInfo(int hLevel, int vLevel, TreeNode node) {
            this.hLevel = hLevel;
            this.vLevel = vLevel;
            this.node = node;
        }
    }
}

Complexity

Time: O(nlogn)
Space: O(height)

dereklisdr commented 2 years ago

class Solution { public static List> verticalTraversal(TreeNode root) { List> ans = new ArrayList<>(); Map>> map = new TreeMap<>(); Queue q = new LinkedList<>(); q.add(new Three(0, 0, root)); while(!q.isEmpty()) { Three curr = q.poll(); if (map.containsKey(curr.hd)) { if (map.get(curr.hd).containsKey(curr.level)) { map.get(curr.hd).get(curr.level).add(curr.n.val); }else { List ls = new ArrayList<>(); ls.add(curr.n.val); map.get(curr.hd).put(curr.level, ls); } }else { List ls = new ArrayList<>(); ls.add(curr.n.val); Map> innermap = new TreeMap<>(); innermap.put(curr.level, ls); map.put(curr.hd, innermap); } if (curr.n.left != null) { q.add(new Three(curr.hd - 1, curr.level + 1, curr.n.left)); } if (curr.n.right != null) { q.add(new Three(curr.hd + 1, curr.level + 1, curr.n.right)); } } for(Map> m : map.values()) { List inner = new ArrayList<>(); for(List l : m.values()) { Collections.sort(l); inner.addAll(l); } ans.add(inner); } return ans; } } class Three { int hd; int level; TreeNode n; public Three(int hd, int level, TreeNode n) { this.hd = hd; this.level = level; this.n = n; } }

Whisht commented 2 years ago

思路

先遍历记录下每个元素的行列值，然后再根据（列，行，值）进行排序。
由于题中要求按列优先，所以三元组种把列排在第一个元素。

python 中 sorted 函数可以对元组进行排序，按照各元素升序进行排序，先根据第一个元素排序，再根据第二个元素排序，正好满足题中要求。

代码：

# 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]]:
    self.info = []
    self.dfs(root,0,0)

    info = sorted(self.info)
    ans = [[]]
    pre_col = info[0][0]
    for col,row,val in info:
        if col == pre_col:
            ans[-1].append(val)
        else:
            ans.append([val])
            pre_col = col
    return ans

def dfs(self,root,row,col):
    if not root:
        return None
    self.info.append((col,row,root.val))
    self.dfs(root.left,row+1,col-1)
    self.dfs(root.right,row+1,col+1)

复杂度：

T: $O(N\log(n))$，主要是排序的复杂度； S: $O(N)$需要存储树中各元素值。

shiyishuoshuo commented 2 years ago

code

class Triplet<F, S, T> {
    public final F first;
    public final S second;
    public final T third;

    public Triplet(F first, S second, T third) {
        this.first = first;
        this.second = second;
        this.third = third;
    }
}

class Solution {
    List<Triplet<Integer, Integer, Integer>> nodeList = new ArrayList<>();

    private void DFS(TreeNode node, Integer row, Integer column) {
        if (node == null)
            return;
        nodeList.add(new Triplet(column, row, node.val));
        // preorder DFS traversal
        this.DFS(node.left, row + 1, column - 1);
        this.DFS(node.right, row + 1, column + 1);
    }

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

        // step 1). DFS traversal
        DFS(root, 0, 0);

        // step 2). sort the list by <column, row, value>
        Collections.sort(this.nodeList, new Comparator<Triplet<Integer, Integer, Integer>>() {
            @Override
            public int compare(Triplet<Integer, Integer, Integer> t1,
                    Triplet<Integer, Integer, Integer> t2) {
                if (t1.first.equals(t2.first))
                    if (t1.second.equals(t2.second))
                        return t1.third - t2.third;
                    else
                        return t1.second - t2.second;
                else
                    return t1.first - t2.first;
            }
        });

        // step 3). extract the values, grouped by the column index.
        List<Integer> currColumn = new ArrayList();
        Integer currColumnIndex = this.nodeList.get(0).first;

        for (Triplet<Integer, Integer, Integer> triplet : this.nodeList) {
            Integer column = triplet.first, value = triplet.third;
            if (column == currColumnIndex) {
                currColumn.add(value);
            } else {
                output.add(currColumn);
                currColumnIndex = column;
                currColumn = new ArrayList();
                currColumn.add(value);
            }
        }
        output.add(currColumn);

        return output;
    }
}

lsunxh commented 2 years ago

Time: O(N logN), Space: O(N)

class Solution(object):
    def __init__(self):
        self.list = []

    def recurse(self, root, col, row):
        if root == None:
            return
        self.list.append((col, row, root.val))
        self.recurse(root.left, col - 1, row + 1)
        self.recurse(root.right, col + 1, row + 1)

    def verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        self.recurse(root, 0, 0)
        res = [[]]
        self.list.sort()
        curCol = self.list[0][0]
        for c, r, v in self.list:
            if c == curCol:
                res[-1].append(v)
            else:
                curCol = c
                res.append([v])
        return res

xi2And33 commented 2 years ago

···js 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);

} }; ···

lbc546 commented 2 years ago

DFS preorder

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

        columnTable = defaultdict(list)
        min_column = max_column = 0

        def DFS(node, row, column):
            if node is not None:
                nonlocal min_column, max_column
                columnTable[column].append((row, node.val))
                min_column = min(min_column, column)
                max_column = max(max_column, column)

                DFS(node.left, row + 1, column - 1)
                DFS(node.right, row + 1, column + 1)

        DFS(root, 0, 0)

        result = []
        for col in range(min_column, max_column + 1):
            result.append([val for row, val in sorted(columnTable[col])])

        return result

Complexity O(nlogn)

zzzkaiNS commented 2 years ago

思路

利用 dfs 将二叉树各个节点编号存储；

排序，并将排序好的数组输出

代码

class Solution {
public:
map<int, vector<vector<int>>> S;
void dfs(TreeNode* root, int x, int y) {
    if (!root) return ;
    S[y].push_back({x, root->val});
    dfs(root->left, x + 1, y - 1);
    dfs(root->right, x + 1, y + 1);
}
vector<vector<int>> verticalTraversal(TreeNode* root) {
    dfs(root, 0, 0);
    vector<vector<int>> res;
    for(auto& [k, v] : S) {
        sort(v.begin(), v.end());
        vector<int> col;
        for (auto& p : v) col.push_back(p[1]);
        res.push_back(col);
    }
    return res;
}
};

wsmmxmm commented 2 years ago

// 害，确实不会写，dfs处理的也很妙，想不出来。最后计算res也想不出 // 新增知识点：Sorting an ArrayList according to user defined criteria. We can use Comparator Interface for this purpose. // In this case: // 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]; // });

class Solution { Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val public List<List> 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> res = new ArrayList<List>(); for(int i = 0; i < n ;){ int j = i; List temp = new ArrayList<>(); while (j < n && list.get(j)[0] == list.get(i)[0]){ temp.add(list.get(j++)[2]); } res.add(temp); i = j; } return res; } public void dfs(TreeNode root){ 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); } } }

ZOULUFENG commented 2 years ago

day18

使用语言：python

使用时间2h10min

没有任何技巧，全是陷在细节中抠细节。学会了怎么使用lambda做函数的参数进行多条件排序

9 class Solution:
10     def __init__(self):
11         self.a_list = []
12         self.b_list = []
13         self.c_list = []
14 
15     def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
16         self.traverse(root, 0, 0)
17         return self.devide_grope(self.a_list)
18 
19         # print(self.b_list)
20 
21     def traverse(self, root, row, col):
22         if not root:
23             return None
24         self.a_list.append([row, col, root.val])
25         self.traverse(root.left, row + 1, col - 1)
26         self.traverse(root.right, row + 1, col + 1)
27 
28     def devide_grope(self, data):
29         self.b_list = sorted(data, key=lambda x: (x[1], x[0], x[2]))
30         b_list = []
31         c_list = []
32 
33         for i in self.b_list:
34             if i[1] not in c_list:
35                 c_list.append(i[1])
36                 b_list.append('#')
37 
38             b_list.append(i[2])
39 
40         row = b_list.count('#')
41         a_list = [[] for _ in range(row)]
42         print(b_list)
43 
44         num = -1
45         for i in b_list:
46             if i == '#':
47                 num += 1
48             else:
49                 a_list[num].append(i)
50         return a_list

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

涉及递归的两个复杂度还是不会计算

nikojxie commented 2 years ago

思路

首先递归遍历，把相同列的数据先塞到一起，通过一个map存储，key为列号，value为该列数据的集合，数据记录了节点的value和所处的row；然后遍历得到的map，先按key，也就是所处的列号从小到大排，同一列的数据如果row相同则以val从小到大排，否则按row从小到大排

代码

var verticalTraversal = function(root) {
  let map = {};
  function dfs (node, row, col) {
    if(node) {
      if(map[col]) map[col].push({row: row, val:node.val})
      else map[col] = [{row: row, val:node.val}]
      dfs(node.left, row + 1, col - 1)
      dfs(node.right, row + 1, col + 1)
    }
  }
  dfs(root, 0 , 0)
  let res = []
  Object.keys(map).sort((x,y) => x-y).forEach(key => {
    res.push(map[key].sort((x,y) => {
      if(x.row === y.row) return x.val - y.val
      else return x.row - y.row
    }).map(e => e.val))
  })
  return res
};

nickyk319 commented 2 years ago

思路

Record the coordinates corresponding to each node.
Traverse the tree first to generate all the coordianates.
Sort the coordinates array as requested.
Add the node to the list if they are in the same column.

代码

class Solution {
    // build the coordinates of node have with attributes
    class Coordinates {
        public int row, col;
        public TreeNode node;

        public Coordinates(TreeNode node, int row, int col) {
            this.node = node;
            this.row = row;
            this.col = col;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        // traverse the binary tree, generate corresponding coordinates
        traverse(root, 0, 0);
        // sort the node
        Collections.sort(nodes, (Coordinates a, Coordinates b) -> {
            if (a.col == b.col && a.row == b.row) {
                return a.node.val - b.node.val;
            }
            if (a.col == b.col) {
                return a.row - b.row;
            }
            return a.col - b.col;
        });

        LinkedList<List<Integer>> res = new LinkedList<>();
        int preCol = Integer.MIN_VALUE;
        for (int i = 0; i < nodes.size(); i++) {
            Coordinates cur = nodes.get(i);
            // check if the column of the current node == previous node
            if (cur.col != preCol) {
                // start to record a new column
                res.add(new LinkedList<>());
                preCol = cur.col;
            }
            // add value to the new added column
            res.getLast().add(cur.node.val);
        }
        return res;
    }

    ArrayList<Coordinates> nodes = new ArrayList<>();
    // traverse the binary tree, store all the nodes with their coordinates in an arrayList
    void traverse(TreeNode root, int row, int col) {
        if (root == null) return;
        nodes.add(new Coordinates(root, row, col));
        traverse(root.left, row + 1, col - 1);
        traverse(root.right, row + 1, col + 1);
    }
}

复杂度分析

时间复杂度：O(NlogN), because of the sorting algo
空间复杂度：O(N), N is numbers of nodes.

azl397985856 commented 2 years ago

test

maoting commented 2 years ago

思路：

看了题解 DFS遍历然后按照要求排序，按照列、行、值排序

代码

 /**
 * @param {TreeNode} root
 * @return {number[][]}
 */

 var verticalTraversal = function(root) {
    const nodes = [];
    dfs(root, 0, 0, nodes);
     // 排序后
    // [ [ -1, 1, 9 ], [ 0, 0, 3 ], [ 0, 2, 15 ], [ 1, 1, 20 ], [ 2, 2, 7 ] ]
    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], 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);
}

复杂度分析

时间复杂度O(nlogn) O(N)对数组进行遍历、O(nlogn)对数组进行排序
空间复杂度O(N)

Tlntin commented 2 years ago

题目链接

链接

代码

/**
 * Definition for a binary tree node.
 * 
 */
#include <vector>
#include <map>
#include <algorithm>
#include <string>

using std::string;
using std::vector;

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 Location {
 public:
  int row;
  int value;
  Location(int row, int val): row(row), value(val){};
  bool operator < (const Location & x) const {
    if (row < x.row) {
      return true;
    } else if (row == x.row && value < x.value) {
      return true;
    } else {
      return false;
    }
  }
};
class Solution {
public:
  vector<vector<int>> verticalTraversal(TreeNode* root) {
    // 思路？先用bfs打印一下，顺便收集节点的行列值，然后按列进行排序？
    // 当x, y相同时，list才需要排序
    // 考虑排序，所以还是用bfs更好
    std::map<int, std::vector<Location>> dict1;
    get_location(root, 0, 0, dict1);
    // 然后遍历dict,对value进行排序
    std::vector<std::vector<int>> result;
    for (auto & x: dict1) {
      if (x.second.size() == 1) {
        std::vector<int> temp_list({x.second[0].value});
        result.push_back(std::move(temp_list));
      } else {
        std::sort(x.second.begin(), x.second.end());
        std::vector<int> temp_list(x.second.size());
        for (int i = 0; i < x.second.size(); ++i) {
          temp_list[i] = x.second[i].value;
        }
        result.push_back(std::move(temp_list));
      }
    }
    return std::move(result);

  }

  void get_location(
    TreeNode * root, int row, int col, std::map<int, std::vector<Location>> & dict1) {

    if (root) {
      // 先判断col是否在root中
      if (dict1.count(col)) {
        std::vector<Location> temp_list(std::move(dict1.at(col)));
        temp_list.push_back(Location(row, root->val));
        dict1[col] = temp_list;
      } else {
        std::vector<Location> temp_list({Location(row, root->val)});
        dict1[col] = temp_list;
      }
      // 然后遍历左右节点
      if (root->left) {
        get_location(root->left, row + 1, col - 1, dict1);
      }
      if (root->right) {
        get_location(root->right, row + 1, col + 1, dict1);
      }
    }
  }
};

复杂度

时间，sort那里占用最大，$O(n*log(n))$
空间：$O(n)$

优化？

不用内置排序，将Location换成dict
减少中间变量创建

结果

hyqqq22 commented 2 years ago

思路

先对树进行遍历，记录每个节点的坐标和值，题中的遍历规则事实上就是自定义规则排序：先后按照col,raw,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: TreeNode) -> List[List[int]]:
        nodes=[]
        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=[]
        precol=-inf
        for i in range(len(nodes)):
            if nodes[i][0]!=precol:
                ans.append([])
                precol=nodes[i][0]
            ans[-1].append(nodes[i][2])
        return ans

复杂度分析

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

suukii commented 2 years ago

Time: $O(NlogN)$, N is the number of tree nodes. The time of traversing the binary tree is $O(N)$ and the time of sorting all the tree nodes is $O(NlogN)$.

Space: $O(N)$

/**
* 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:
using Point = tuple<int, int, int>;
vector<vector<int>> verticalTraversal(TreeNode* root) {
    vector<Point> coordinates;
    getCoordinates(root, 0, 0, coordinates);
    sort(coordinates.begin(), coordinates.end(), sortPoints);

    vector<vector<int>> res;
    res.reserve(coordinates.size());
    int last_x = INT_MIN;
    for (const auto& p : coordinates) {
        auto [x, y, v] = p;
        if (x > last_x) {
            res.push_back(vector<int>());
            last_x = x;
        }
        res.back().push_back(v);
    }

    return res;
}
private:
void getCoordinates(TreeNode* root, int x, int y, vector<Point>& coordinates) {
    if (!root) return;
    coordinates.push_back({x, y, root->val});
    getCoordinates(root->left, x - 1, y + 1, coordinates);
    getCoordinates(root->right, x + 1, y + 1, coordinates);
}

static int sortPoints(const Point& a, const Point& b) {
    auto [ax, ay, av] = a;
    auto [bx, by, bv] = b;
    if (ax == bx && ay == by) return av < bv;
    if (ax == bx) return ay < by;
    return ax < bx;
}
};

thinkfurther commented 2 years ago

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return None
        q = collections.deque()
        q.append((root,0,0))
        result = collections.defaultdict(list)

        while q:
            n = len(q)

            for _ in range(n):
                node, col, row = q.popleft()
                result[(col,row)].append(node.val)                

                if node.left:
                    q.append((node.left,col-1, row+1))

                if node.right:
                    q.append((node.right,col+1, row+1))

        sorted_result = sorted(result.items(), key = lambda x: x[0])        
        print(sorted_result)

        final_result = []
        current_col, _ = sorted_result[0][0]
        current_col_data = []

        for i in range(len(sorted_result)):
            next_col, next_row = sorted_result[i][0]
            next_data = sorted_result[i][1]

            if next_col != current_col:
                final_result.append(current_col_data)
                current_col_data = sorted(next_data)
                current_col = next_col
            else:
                current_col_data.extend(sorted(next_data))
                print(current_col_data)
        final_result.append(current_col_data)        

        return final_result

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

nuomituxedo commented 2 years ago

思路

Step 1: use recursion to travel through the tree to build a list containing each node's [value, row col] values.

Step 2: construct a nested dictionary where the key is col, value is a dict where the row is key, and a list of values as value.

Step 3: construct result from above dictionary

code


class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        #Step 1: recursively (DFS) map each node with its value, row and col
        #res becomes a list containing lists of such value, row, col pairs
        def mapper(root, res, row, col):
            if not root:
                return
            res.append([root.val, row, col])
            mapper(root.left, res, row+1, col-1)
            mapper(root.right, res, row+1, col+1)
            return res

        #nodes is a list containing lists. Each list contains a node's value, row, col 
        nodes = mapper(root, [], 0, 0)

        #Step 2: create a dictionary where key is the col value, values is a list of node values 
        verticalOrderTraversal = {}
        for node in nodes:
            val = node[0]
            row = node[1]
            col = node[2]
            if col in verticalOrderTraversal:
                if row in verticalOrderTraversal[col]:
                    verticalOrderTraversal[col][row].append(val)
                    print('exisitng row, add val to list',verticalOrderTraversal[col][row] )
                else:
                    newList = [val]
                    verticalOrderTraversal[col][row] = newList
                    print('adding new row', newList, verticalOrderTraversal[col][row] )
            else:
                newColDict = {}
                newColDict[row] = [val]
                verticalOrderTraversal[col] = newColDict

        #Sort the dictionary by column key
        sortedTraversal = dict(sorted(verticalOrderTraversal.items(), key=lambda x:x[0]))

        #Sort the dictionary by row key
        for col in sortedTraversal:
            sortedTraversal[col] = dict(sorted(sortedTraversal[col].items(), key=lambda x:x[0]))

        #Step 3: create the final result from the dictionary with sorted keys
        resultList = []
        for col in sortedTraversal.keys():
            item = []
            for row in sortedTraversal[col]:
                #before adding the value list to resultList, remember to sort the list
                for value in sorted(sortedTraversal[col][row]):
                    item.append(value)
            resultList.append(item)
        return resultList

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

ccslience commented 2 years ago

1.思路: 带记录(x,y)的dfs, 用map来存, map是自带排序的;
2.思路分析: 刚开始看成对同一列的进行排序, 后面才看到是同行同列才排序, 因此用 map<int, map<int, vector>>结构;
3.时间复杂度:O(nlogn)(主要是排序的时间), 空间复杂度:O(n)(map存的总结点数为树的结点数).
*/

class Solution
{
public:
    void dfs(TreeNode * root, int row, int col)
    {
        // 当前操作
        if(info.find(col) == info.end() || info[col].find(row) == info[col].end())
            info[col][row] = vector<int>(1, root->val);
        else
            info[col][row].push_back(root->val);
        // 判断退出条件
        if(root->left == nullptr && root->right == nullptr)
            return;

        // 进入下一次循环
        if(root->left)
            dfs(root->left, row + 1, col - 1);
        if(root->right)
            dfs(root->right, row + 1, col + 1);
    }
    vector<vector<int>> verticalTraversal(TreeNode * root)
    {
        vector<vector<int>> res;
        dfs(root, 0, 0);
        for(auto i: info)
        {
            vector<int> tmp;
            for(auto it : i.second)
            {
                sort(it.second.begin(), it.second.end());
                for(auto it1: it.second)
                    tmp.push_back(it1);
            }
            res.push_back(tmp);
        }
        return res;

    }
private:
    // 每列存一个hash表，每列的hash表主键为行号, 这里用map, map里面存的就是按key排序的, 因此不用单独对列排序，行同理
    map<int, map<int, vector<int>>> info;
};

HackBL commented 2 years ago


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

        TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new TreeMap<>();
        dfs(root, 0, 0, map);

        for (TreeMap<Integer, PriorityQueue<Integer>> entry : map.values()) {
            res.add(new ArrayList<>());

            for (PriorityQueue<Integer> pq : entry.values()) {
                while (!pq.isEmpty()) {
                    res.get(res.size()-1).add(pq.poll());       
                }
            }
        }

        return res;
    }

    public void dfs(TreeNode root, int x, int y, TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map) {
        if (root == null) return;

        if (!map.containsKey(x)) {
            map.put(x, new TreeMap<>());
        }

        if (!map.get(x).containsKey(y)) {
            map.get(x).put(y, new PriorityQueue<>());
        }

        map.get(x).get(y).add(root.val);

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

zch-bit commented 2 years ago

Day 18

import "sort"

type XTreeNode struct {
    t *TreeNode
    X int
}

func verticalTraversal(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }

    solutions := make(map[int][]int) // X -> elems ordered by Y and X
    notevaluated := []XTreeNode { XTreeNode{ root, 0} }
    minX := 0

    for len(notevaluated) > 0 {
        sort.Slice(notevaluated, func (i, j int) bool {
            if notevaluated[i].X > notevaluated[j].X {
                return false
            }
            if notevaluated[i].X < notevaluated[j].X {
                return true
            } else {
                return notevaluated[i].t.Val < notevaluated[j].t.Val
            }
        })
        evaluatenext := make([]XTreeNode, 0, len(notevaluated)*2)
        for _, v := range notevaluated {
            solutions[v.X] = append(solutions[v.X], v.t.Val)
            if v.X < minX {
                minX = v.X
            }
            if v.t.Left != nil {
                evaluatenext = append(evaluatenext, XTreeNode{v.t.Left, v.X-1})
            }
            if v.t.Right != nil {
                evaluatenext = append(evaluatenext, XTreeNode{v.t.Right, v.X+1})
            }
        }
        notevaluated = evaluatenext
    }

    ret := make([][]int, len(solutions))
    for k, v := range solutions {
        ret[k-minX] = v
    }
    return ret
}

ceramickitten commented 2 years ago

思路

利用dfs进行搜索，hash表聚合每一列的结果，对key和value进行排序保证符合题目的顺序

代码


class Solution:
    def dfs(self,
            node: TreeNode,
            row: int,
            col: int,
            col_to_row_val_dict: Dict[int, List[Tuple[int, int]]]) -> None:
        if not node:
            return
        col_to_row_val_dict[col].append((row, node.val))
        self.dfs(node.left, row + 1, col - 1, col_to_row_val_dict)
        self.dfs(node.right, row + 1, col + 1, col_to_row_val_dict)

    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        col_to_row_val_dict = defaultdict(lambda : [])
        self.dfs(root, 0, 0, col_to_row_val_dict)
        result = []
        for col in sorted(col_to_row_val_dict.keys()):
            vals = [val for row, val in sorted(col_to_row_val_dict[col])]
            result.append(vals)
        return result

复杂度分析

Time: O(nlogn) dfs遍历O(n), 排序key和每一列的值O(nlogn)
Space: O(n) 递归栈O(logn)，哈希表O(n)

y525 commented 2 years ago

def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]: dq, hash_table = deque(), {} dq.append([root, 0 , 0]) hash_table[(0, 0)] = [root.val] while dq: node, row, col = dq.popleft() if node.left: dq.append([node.left, row + 1, col - 1]) if (row + 1, col - 1) not in hash_table: hash_table[(row + 1, col - 1)] = [] hash_table[(row + 1, col - 1)].append(node.left.val) if node.right: dq.append([node.right, row + 1, col + 1]) if (row + 1, col + 1) not in hash_table: hash_table[(row + 1, col + 1)] = [] hash_table[(row + 1, col + 1)].append(node.right.val)

    keys = list(hash_table.keys())
    keys.sort(key = lambda x: [x[1], x[0]])
    result = []
    last_col = - float('Inf')
    for key in keys:
        if key[1] > last_col:
            result.append([])
            last_col = key[1]
        result[-1] += sorted(hash_table[key])
    return result

wzasd commented 2 years ago

思路

思路就是还是dfs 再加上 TreeMap，只是比较麻烦的是要对高度的进行分析排序（同高的位置），因此数据模式就比较麻烦，而且需要两次循环，但还好最多同一高度有两个节点所以速度不会有很大效率问题

代码

    Map<Integer, Map<Integer, List<Integer>>> ans = new TreeMap<>();
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> ansList = new ArrayList<>();
        dfs(root, 0, 0);
        for (Map.Entry<Integer, Map<Integer, List<Integer>>> entry : ans.entrySet()) {
            List<Integer> list = new ArrayList<>();
            for (Map.Entry<Integer, List<Integer>> heightEntry : entry.getValue().entrySet()) {
                list.addAll(heightEntry.getValue());
            }
            ansList.add(list);
        }
        return ansList;
    }

    public void dfs(TreeNode node, int column, int height) {
        if (node == null) {
            return;
        }
        ++height;
        if (ans.containsKey(column)) {
            if (ans.get(column).containsKey(height)) {
                ans.get(column).get(height).add(node.val);
                Collections.sort(ans.get(column).get(height));
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(node.val);
                ans.get(column).put(height, list);
            }
        } else {
            List<Integer> list = new ArrayList<>();
            list.add(node.val);
            Map<Integer, List<Integer>> map = new TreeMap<>();
            map.put(height, list);
            ans.put(column, map);
        }
        dfs(node.left, column - 1, height);
        dfs(node.right, column + 1, height);
    }

xixiao51 commented 2 years ago

Idea

Use dfs to generate a list contains x, y and val for each node. Then sort the list. From the sorted list, we then extract the results, and group them by the column index.

Code

class Solution {
    List<List<Integer>> nodeList = new ArrayList();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        if(root == null) {
            return res;
        }
        dfs(root, 0, 0);
        // sort the node
        Collections.sort(nodeList, (List<Integer> a, List<Integer> b) -> {
            if (a.get(1) == b.get(1) && a.get(0) == b.get(0)) {
                return a.get(2) - b.get(2);
            }
            if (a.get(1) == b.get(1)) {
                return a.get(0) - b.get(0);
            }
            return a.get(1) - b.get(1);
        });
        int column = nodeList.get(0).get(1);
        List<Integer> arr = new ArrayList<>();
        for(List<Integer> l: nodeList) {
            int y = l.get(1);
            int val = l.get(2);
            if(column == y) {
                arr.add(val);
            } else {
                res.add(arr);
                column = y;
                arr = new ArrayList<>();
                arr.add(val);
            }
        }
        res.add(arr);

        return res;
    }

    private void dfs(TreeNode node, int x, int y) {
        if(node == null) {
            return;
        }
        nodeList.add(Arrays.asList(x, y, node.val));
        dfs(node.left, x + 1, y - 1);
        dfs(node.right, x + 1, y + 1);
    }
}

Complexity Analysis

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

2learnsomething commented 2 years ago

思路

bfs,又有点像模拟

代码

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        order = []
        deque = collections.deque([(root,0,0)])
        col_list = list()
        while deque:
            for _ in range(len(deque)):
                node,row,col = deque.popleft()
                if col not in col_list: col_list.append(col)
                order.append((col,row,node.val))
                if node.left:
                    deque.append((node.left,row+1,col-1))
                if node.right:
                    deque.append((node.right,row+1,col+1))
        ans = []
        col_list.sort()
        order.sort()
        for c in col_list:
            temp = []
            while order and order[0][0] == c:
                temp.append(heapq.heappop(order)[2])
            ans.append(temp)
        return ans

复杂度

时间复杂度:O(N) 空间复杂度:O(N)

dujt-X commented 2 years ago

思路

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

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

代码实现

C++

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<tuple<int, int, int>> nodes;

        function<void(TreeNode*, int, int)> dfs = [&](TreeNode* node, int row, int col) {
            if (!node) {
                return;
            }
            nodes.emplace_back(col, row, node->val);
            dfs(node->left, row + 1, col - 1);
            dfs(node->right, row + 1, col + 1);
        };

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

复杂度分析

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

kernelSue commented 2 years ago

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root.left == null && root.right == null){
            List<Integer> list = new ArrayList<>();
            list.add(root.val);
            res.add(list);
            return res;
        }
        Map<Integer, Map<TreeNode, Integer>> maps = new HashMap<>();
        DFSearch(root, maps, 0, 0);
        maps.keySet().stream().sorted().forEachOrdered(e -> res.add(mySort(maps.get(e))));
        return res;
    }
    private void DFSearch(TreeNode x, Map<Integer, Map<TreeNode, Integer>> maps, int col, int row){
        if(x == null)  return;

        if(maps.get(col) == null){
            Map<TreeNode, Integer> map = new HashMap<>();
            map.put(x, row);
            maps.put(col, map);
        }
        else  maps.get(col).put(x, row);
        DFSearch(x.left, maps, col-1, row+1);
        DFSearch(x.right, maps, col+1, row+1);
    }
    private List<Integer> mySort(Map<TreeNode, Integer> m){
        List<Integer> list = new ArrayList<>();
        m.entrySet().stream().sorted(new Comparator<Map.Entry<TreeNode, Integer>>() {
            @Override
            public int compare(Map.Entry<TreeNode, Integer> o1, Map.Entry<TreeNode, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0)  return o1.getKey().val - o2.getKey().val;
                else  return o1.getValue().compareTo(o2.getValue());
            }
        }).forEachOrdered(e -> list.add(e.getKey().val));
        return list;
    }
}

UCASHurui commented 2 years ago

思路

遍历一遍二叉树的节点，保存节点的横纵坐标和节点的值，根据纵坐标，横坐标，节点的值依次排序，再遍历一遍将每一列的节点的值取出。

代码

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        nodes = []
        def dfs(root, row, col):
            if not root: return None
            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.sort()
        ans = []
        i = j = 0
        while i < len(nodes):
            col_ans = []
            while j< len(nodes) and nodes[j][0] == nodes[i][0]:
                col_ans.append(nodes[j][2])
                j += 1
            ans.append(col_ans)
            i = j
        return ans

复杂度分析

时间复杂度：O(NlogN),N是节点的数量
空间复杂度：O(N)

Jakkiabc commented 2 years ago

class Solution:

def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
    # DFS求坐标
    hashmap = collections.defaultdict(list)
    def dfs(node, j, i):
        if not node:
            return
        hashmap[(j, i)].append(node.val)
        dfs(node.left, j - 1, i + 1)
        dfs(node.right, j + 1, i + 1)
    dfs(root, 0, 0) # 排序
    res, tmp= [], []
    j_flag = -1001
    for j, i in sorted(hashmap.keys()):
        if j != j_flag:
            res.append(tmp)
            tmp = []
            j_flag = j
        tmp.extend(sorted(hashmap[(j, i)]))
    res.pop(0)
    res.append(tmp)
    return res`

testplm commented 2 years ago


class Solution:
    def __init__(self):
        self.point_list = []

    def dfs(self, root, x, y):
        self.point_list.append([x,y,root.val]) # keep in list all points
        if root.left:
            self.dfs(root.left, x-1, y-1)
        if root.right:
            self.dfs(root.right, x+1, y-1)

    def verticalTraversal(self, root):
        self.dfs(root, 0, 0)
        self.point_list.sort(key = lambda a:a[2]) # sort by value
        self.point_list.sort(key = lambda a:a[1], reverse = True) # sort by y
        self.point_list.sort(key = lambda a:a[0]) # sort by x

        res = []
        left = abs(self.point_list[0][0])
        right = self.point_list[-1][0]

        for i in range(left+right+1):
            res.append([j[2] for j in self.point_list if j[0]==i-left])

        return res

caterpillar-0 commented 2 years ago

思路

首先深度遍历，将节点的xy存储，排序部分利用struct结构体重载<运算符，在优先队列中实现排序，最后再输出到res数组中

代码

class Solution {
public:
    struct Node{
        int x,y,val;
        Node(){}//重写构造函数，就要写默认构造
        Node(int x,int y,int val):x(x),y(y),val(val){}
        //重点在于重载<号,默认为大顶堆，<，从小到大
        bool operator <(Node node)const{
            if(y!=node.y)return y>node.y;
            else if(x!=node.x)return x>node.x;
            else return val>node.val;
        }
    };
    map<int,priority_queue<Node>>myMap;
    //首先，深度遍历，递归，确定每个节点的x,y值
    void dfs(TreeNode* root,int x,int y){//root当前的x,y值
        if(root==nullptr)return;
        myMap[y].push({x,y,root->val});
        if(root->left)dfs(root->left,x+1,y-1);
        if(root->right)dfs(root->right,x+1,y+1);
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        vector<vector<int>>res;
        if(root==nullptr)return res;
        dfs(root,0,0);
        for(auto& [x,y]:myMap){
            res.push_back(vector<int>());
            while(!y.empty()){
                res.back().push_back(y.top().val);
                y.pop();
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度:o(nlogn)
空间复杂度:o(n)

tian-pengfei commented 2 years ago

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        //           col row value
        vector<tuple<int,int,int>> lst ;

        preOrder(lst,root,0,0);
        sort(lst.begin(),lst.end());

        vector<vector<int>> re;
        re.emplace_back();
        int last_col = get<0>(lst[0]);
        for (auto& t:lst){
            int c_col = get<0>(t);
            int val = get<2>(t);
            if(last_col!=c_col){
                re.emplace_back();
                last_col = c_col;
            }
            re.rbegin()->emplace_back(val);
        }

        return re;

    }

    void preOrder(vector<tuple<int,int,int>>&lst,TreeNode *root,int col,int row){

        if(!root)return;
        lst.emplace_back(col,row,root->val);

        preOrder(lst,root->left,col-1,row+1);
        preOrder(lst,root->right,col+1,row+1);
    }
};

miss1 commented 2 years ago

/**
 * @param {TreeNode} root
 * @return {number[][]}
 * DFS, 先序遍历，记录每个节点的row和col，存储到map中，map中col为key值，value为对象数组[{row: row, val: root.val}]
 * 对map的key排序，遍历key获取map的值，将取出来的数组根据row和val的值排序（先比较row的大小，row相同再比较val），再将排序好的数组push到结果数组res中
 * {0：[{row: row, val: root.val}]}
 * time: O(nlogn), sort排序的时间复杂度为O(nlogn)
 * space: O(n)
 */
var verticalTraversal = function(root) {
  let map = new Map();
  let keys = [], res = [];
  let preOrder = function(root, row, col) {
    if (!root) return;
    if (map.has(col)) map.get(col).push({row: row, val: root.val});
    else {
      map.set(col, [{row: row, val: root.val}]);
      keys.push(col);
    }
    preOrder(root.left, row + 1, col - 1);
    preOrder(root.right, row + 1, col + 1);
  };
  preOrder(root, 0, 0);
  keys.sort((a,b) => { return a - b; });
  for (let i = 0; i < keys.length; i++) {
    let arr = map.get(keys[i]);
    arr.sort((a,b) => {
      if (a.row === b.row) return a.val - b.val;
      else return a.row - b.row;
    });
    res.push(arr.map(val => {return val.val}));
  }
  return res;
};

Xinyi-arch commented 2 years ago

思路

BFS，使用双向队列储存，依次遍历，根据横坐标储存至字典

code

class Solution(object):
    def verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]] """

        if root is None: return []
        queue, d = deque([[root, 0, 0]]), {}
        while queue:
            for _ in range(len(queue)):
                node, x, y = queue.popleft()
                node.left and queue.append([node.left, x - 1, y + 1])
                node.right and queue.append([node.right, x + 1, y + 1])
                d.setdefault(x, []).append((y, node.val))
        return [list(map(itemgetter(1), sorted(d[k]))) for k in sorted(d)]

luckyoneday commented 2 years ago

思路

（抄的题解，太菜了这个不太会

代码 js

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

复杂度

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

Cusanity commented 2 years ago

Solution

Language: Java

class Solution {
    class Triple {
        public int row, col;
        public TreeNode node;
        public Triple(TreeNode node, int row, int col) {
            this.node = node;
            this.row = row;
            this.col = col;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        traverse(root, 0, 0);
        Collections.sort(nodes, (Triple a, Triple b) -> {
            if (a.col == b.col && a.row == b.row) {
                return a.node.val - b.node.val;
            }
            if (a.col == b.col) {
                return a.row - b.row;
            }
            return a.col - b.col;
        });
        LinkedList<List<Integer>> res = new LinkedList<>();
        int preCol = Integer.MIN_VALUE;
        for (int i = 0; i < nodes.size(); i++) {
            Triple cur = nodes.get(i);
            if (cur.col != preCol) {
                res.addLast(new LinkedList<>());
                preCol = cur.col;
            }
            res.getLast().add(cur.node.val);
        }

        return res;
    }

    ArrayList<Triple> nodes = new ArrayList<>();
    void traverse(TreeNode root, int row, int col) {
        if (root == null) {
            return;
        }
        nodes.add(new Triple(root, row, col));
        traverse(root.left, row + 1, col - 1);
        traverse(root.right, row + 1, col + 1);
    }
}

xqy97 commented 2 years ago

题目描述

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

解题思路

dfs遍历每一个节点，记录每个节点的，colIndex, rowIndex, value
按列，行，值，把所有节点排序
同一行同一列的节点放进一个数组

代码

var verticalTraversal = function(root) {
    let nodeList = []
    dfs(root, 0, 0, nodeList)
    nodeList.sort((pre, cur) => {
        if(pre[0] !== cur[0]) {
            return pre[0] - cur[0]
        } else if (pre[1] !== cur[1]) {
            return pre[1] - cur[1]
        } else {
            return pre[2] - cur[2]
        }
    })
    let res = []
    let lastCol = -Number.MAX_VALUE
    for(let node of nodeList) {
        if (node[0] !== lastCol) {
            lastCol = node[0]
            res.push([])
        }
        res[res.length - 1].push(node[2])
    }
    return res
}

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

复杂度

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

Orangejuz commented 2 years ago

# 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]]:
        dic = collections.defaultdict(list)

        queue = [(0, 0, root)]
        while queue:
            n_q = len(queue)
            for _ in range(n_q):
                i, j, node = queue.pop(0)
                dic[j].append((i, node.val))
                if node.left:
                    queue.append((i + 1, j - 1, node.left))
                if node.right:
                    queue.append((i + 1, j + 1, node.right))

        res = []
        arr = sorted(dic.keys())
        for k in arr:
            tmp = sorted(dic[k])
            res.append([v[1] for v in tmp])
        return res

xi2And33 commented 2 years ago

var verticalTraversal = function (root) {
    if (!root) return []
    let pos = {}
    dfs(root, 0, 0)

    let sorted = Object.keys(pos).sort((a, b) => +a - +b).map(k => pos[k])

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

};

aiweng1981 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

复杂度

时间复杂度: O(N*log（N）)

空间复杂度: O(N)