Given a binary tree, return the vertical order traversal of its nodes values.
For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).
Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).
If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.
Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.
Example 1:
Input: [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Explanation: Without loss of generality, we can assume the root node is at position (0, 0): Then, the node with value 9 occurs at position (-1, -1); The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2); The node with value 20 occurs at position (1, -1); The node with value 7 occurs at position (2, -2).
Example 2:
Input: [1,2,3,4,5,6,7] Output: [[4],[2],[1,5,6],[3],[7]] Explanation: The node with value 5 and the node with value 6 have the same position according to the given scheme. However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.
Note:
- The tree will have between 1 and
1000nodes. - Each node’s value will be between
0and1000.
Solution: Ordered Map+ Ordered Set
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua, running time: 0 ms, 921.6 KB class Solution { public: vector<vector<int>> verticalTraversal(TreeNode* root) { if (!root) return {}; int min_x = INT_MAX; int max_x = INT_MIN; map<pair<int, int>, multiset<int>> h; // {y, x} -> {vals} traverse(root, 0, 0, h, min_x, max_x); vector<vector<int>> ans(max_x - min_x + 1); for (const auto& m : h) { int x = m.first.second - min_x; ans[x].insert(end(ans[x]), begin(m.second), end(m.second)); } return ans; } private: void traverse(TreeNode* root, int x, int y, map<pair<int, int>, multiset<int>>& h, int& min_x, int& max_x) { if (!root) return; min_x = min(min_x, x); max_x = max(max_x, x); h[{y, x}].insert(root->val); traverse(root->left, x - 1, y + 1, h, min_x, max_x); traverse(root->right, x + 1, y + 1, h, min_x, max_x); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Author: Huahua, 36 ms, 6.8 MB class Solution: def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]': if not root: return [] vals = [] def preorder(root, x, y): if not root: return vals.append((x, y, root.val)) preorder(root.left, x - 1, y + 1) preorder(root.right, x + 1, y + 1) preorder(root, 0, 0) ans = [] last_x = -1000 for x, y, val in sorted(vals): if x != last_x: ans.append([]) last_x = x ans[-1].append(val) return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment