Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/314.html
314 Binary Tree Vertical Order Traversal
Given a binary tree, return the vertical order traversal of its nodes' values.
(ie, from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Examples:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its vertical order traversal as:
[
[9],
[3,15],
[20],
[7]
]
Given binary tree [3,9,20,4,5,2,7],
_3_
/ \
9 20
/ \ / \
4 5 2 7
return its vertical order traversal as:
[
[4],
[9],
[3,5,2],
[20],
[7]
]
@tag-tree
Algorithm
How to determine the order of the columns, you can give the root node a sequence number of 0, and then start the traversal of the layer sequence. For any left child node, the sequence number is reduced by 1, and the right child node sequence number is increased by 1, so that the node value of the same column can be changed by the sequence number Put together
Another way, is to use a TreeMap
to create a mapping between the sequence number and its corresponding node value.
- advantage of using TreeMap is that its
automatic sorting
function allows the column to be sorted from left to right. Since the sequence traversal needs to use the queue, the queue cannot only be stored at this time for nodes, it is necessary to store a pair consisting of a sequence number and a node, so that the sequence number can be operated every time it is taken out, and the nodes in the queue are also assigned their correct sequence numbers.
Code
Java
-
// Time complexity O(n) // Space complexity O(n) public class Solution { private class TreeColumnNode{ public TreeNode treeNode; int col; public TreeColumnNode(TreeNode node, int col) { this.treeNode = node; this.col = col; } } public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null) { return res; } Queue<TreeColumnNode> queue = new LinkedList<>(); Map<Integer, List<Integer>> map = new HashMap<>(); queue.offer(new TreeColumnNode(root, 0)); int curLevelCount = 1; int nextLevelCount = 0; while(!queue.isEmpty()) { TreeColumnNode node = queue.poll(); if(map.containsKey(node.col)) { map.get(node.col).add(node.treeNode.val); } else { map.put(node.col, new ArrayList<Integer>(Arrays.asList(node.treeNode.val))); } curLevelCount--; if(node.treeNode.left != null) { queue.offer(new TreeColumnNode(node.treeNode.left, node.col - 1)); nextLevelCount++; } if(node.treeNode.right != null) { queue.offer(new TreeColumnNode(node.treeNode.right, node.col + 1)); nextLevelCount++; } if(curLevelCount == 0) { curLevelCount = nextLevelCount; nextLevelCount = 0; } } return new ArrayList<List<Integer>>(map.values()); } }
-
// OJ: https://leetcode.com/problems/binary-tree-vertical-order-traversal/ // Time: O(NlogW) where N is the number of nodes in the tree and W is the width of the tree // Space: O(N) class Solution { public: vector<vector<int>> verticalOrder(TreeNode* root) { if (!root) return {}; map<int, vector<int>> m; queue<pair<TreeNode*, int>> q; q.emplace(root, 0); while (q.size()) { auto [node, index] = q.front(); q.pop(); m[index].push_back(node->val); if (node->left) q.emplace(node->left, index - 1); if (node->right) q.emplace(node->right, index + 1); } vector<vector<int>> ans; for (auto &[index, v] : m) ans.push_back(v); return ans; } };
-
# 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 verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if root is None: return [] q = deque([(root, 0)]) d = defaultdict(list) while q: for _ in range(len(q)): root, offset = q.popleft() d[offset].append(root.val) if root.left: q.append((root.left, offset - 1)) if root.right: q.append((root.right, offset + 1)) return [v for _, v in sorted(d.items())] ############ # 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 ''' >>> d = {1:'a', -1:'b', 10:'c', -100:'d'} >>> >>> d.items() {1: 'a', 10: 'c', -100: 'd', -1: 'b'} >>> ds = sorted(d.items()) >>> ds [(-100, 'd'), (-1, 'b'), (1, 'a'), (10, 'c')] >>> sorted(d.items(), key=lambda l: l[1]) [(1, 'a'), (-1, 'b'), (10, 'c'), (-100, 'd')] >>> dict(sorted(d.items(), key=lambda l: l[1])) {1: 'a', 10: 'c', -100: 'd', -1: 'b'} >>> [v for i,v in sorted(d.items(), key=lambda l: l[0])] ['d', 'b', 'a', 'c'] ''' class Solution: def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if root is None: return [] q = deque([(root, 0)]) d = defaultdict(list) while q: for _ in range(len(q)): root, offset = q.popleft() d[offset].append(root.val) if root.left: q.append((root.left, offset - 1)) if root.right: q.append((root.right, offset + 1)) return [v for _, v in sorted(d.items())] ################# from collections import defaultdict class Solution(object): def verticalOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ def dfs(p, i, j, res): # i -> depth, j -> vertical-shift if p: res[j].append((p.val, i)) self.leftMost = min(j, self.leftMost) dfs(p.left, i + 1, j - 1, res) dfs(p.right, i + 1, j + 1, res) self.leftMost = float("inf") ans = [] res = defaultdict(list) dfs(root, 0, 0, res) i = self.leftMost while True: if not res[i]: break ans.append([item[0] for item in sorted(res[i], key=lambda a: a[1])]) i += 1 return ans
TreeMap version
-
// Time complexity O(nlogn) // Space complexity O(n) /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> verticalOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new LinkedList<>(); Queue<Integer> cols = new LinkedList<>(); Map<Integer, List<Integer>> map = new TreeMap<>(); q.offer(root); cols.offer(0); int min = 0, max = 0; while (!q.isEmpty()) { TreeNode cur = q.poll(); int col = cols.poll(); if (!map.containsKey(col)) map.put(col, new ArrayList<>()); map.get(col).add(cur.val); if (cur.left != null) { q.offer(cur.left); cols.offer(col - 1); min = Math.min(min, col - 1); } if (cur.right != null) { q.offer(cur.right); cols.offer(col + 1); max = Math.max(max, col + 1); } } res.addAll(map.values()); return res; } }
-
// OJ: https://leetcode.com/problems/binary-tree-vertical-order-traversal/ // Time: O(NlogW) where N is the number of nodes in the tree and W is the width of the tree // Space: O(N) class Solution { public: vector<vector<int>> verticalOrder(TreeNode* root) { if (!root) return {}; map<int, vector<int>> m; queue<pair<TreeNode*, int>> q; q.emplace(root, 0); while (q.size()) { auto [node, index] = q.front(); q.pop(); m[index].push_back(node->val); if (node->left) q.emplace(node->left, index - 1); if (node->right) q.emplace(node->right, index + 1); } vector<vector<int>> ans; for (auto &[index, v] : m) ans.push_back(v); return ans; } };
-
# 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 verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if root is None: return [] q = deque([(root, 0)]) d = defaultdict(list) while q: for _ in range(len(q)): root, offset = q.popleft() d[offset].append(root.val) if root.left: q.append((root.left, offset - 1)) if root.right: q.append((root.right, offset + 1)) return [v for _, v in sorted(d.items())] ############ from collections import defaultdict class Solution(object): def verticalOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ def dfs(p, i, j, res): if p: res[j].append((p.val, i)) self.leftMost = min(j, self.leftMost) dfs(p.left, i + 1, j - 1, res) dfs(p.right, i + 1, j + 1, res) self.leftMost = float("inf") ans = [] res = defaultdict(list) dfs(root, 0, 0, res) i = self.leftMost while True: if not res[i]: break ans.append([item[0] for item in sorted(res[i], key=lambda a: a[1])]) i += 1 return ans