{"id":4772,"date":"2019-02-02T23:19:39","date_gmt":"2019-02-03T07:19:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4772"},"modified":"2021-12-09T21:21:20","modified_gmt":"2021-12-10T05:21:20","slug":"leetcode-987-vertical-order-traversal-of-a-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-987-vertical-order-traversal-of-a-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 987. Vertical Order Traversal of a Binary Tree"},"content":{"rendered":"\n

Given a binary tree, return the vertical order<\/em> traversal of its nodes values.<\/p>\n\n\n\n

For each node at position (X, Y)<\/code>, its left and right children respectively will be at positions (X-1, Y-1)<\/code> and (X+1, Y-1)<\/code>.<\/p>\n\n\n\n

Running a vertical line from X = -infinity<\/code> to X = +infinity<\/code>, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y<\/code> coordinates).<\/p>\n\n\n\n

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.<\/p>\n\n\n\n

Return an list of non-empty reports in order of X<\/code> coordinate.  Every report will have a list of values of nodes.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>[3,9,20,null,null,15,7]\nOutput: <\/strong>[[9],[3,15],[20],[7]]\nExplanation: <\/strong>\nWithout loss of generality, we can assume the root node is at position (0, 0):\nThen, the node with value 9 occurs at position (-1, -1);\nThe nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);\nThe node with value 20 occurs at position (1, -1);\nThe node with value 7 occurs at position (2, -2).\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Input: <\/strong>[1,2,3,4,5,6,7]\nOutput: <\/strong>[[4],[2],[1,5,6],[3],[7]]\nExplanation: <\/strong>\nThe node with value 5 and the node with value 6 have the same position according to the given scheme.\nHowever, in the report \"[1,5,6]\", the node value of 5 comes first since 5 is smaller than 6.\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. The tree will have between 1 and 1000<\/code> nodes.<\/li>
  2. Each node’s value will be between 0<\/code> and 1000<\/code>.<\/li><\/ol>\n\n\n\n
    Solution: Ordered Map+ Ordered Set<\/strong><\/h2>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 0 ms, 921.6 KB \nclass Solution {\npublic:\n  vector> verticalTraversal(TreeNode* root) {\n    if (!root) return {};\n    int min_x = INT_MAX;\n    int max_x = INT_MIN;\n    map, multiset> h; \/\/ {y, x} -> {vals}\n    traverse(root, 0, 0, h, min_x, max_x);\n    vector> ans(max_x - min_x + 1);\n    for (const auto& m : h) {      \n      int x = m.first.second - min_x;\n      ans[x].insert(end(ans[x]), begin(m.second), end(m.second));\n    }\n    return ans;\n  }\nprivate:\n  void traverse(TreeNode* root, int x, int y, \n                map, multiset>& h,\n                int& min_x,\n                int& max_x) {\n    if (!root) return;\n    min_x = min(min_x, x);\n    max_x = max(max_x, x);    \n    h[{y, x}].insert(root->val);\n    traverse(root->left, x - 1, y + 1, h, min_x, max_x);\n    traverse(root->right, x + 1, y + 1, h, min_x, max_x);\n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua, 36 ms, 6.8 MB\nclass Solution:\n  def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]':\n    if not root: return []    \n    vals = []\n    def preorder(root, x, y):\n      if not root: return\n      vals.append((x, y, root.val))\n      preorder(root.left, x - 1, y + 1)\n      preorder(root.right, x + 1, y + 1)\n    preorder(root, 0, 0)    \n    ans = []\n    last_x = -1000\n    for x, y, val in sorted(vals):\n      if x != last_x:\n        ans.append([])\n        last_x = x\n      ans[-1].append(val)\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[462,177,243,32],"class_list":["post-4772","post","type-post","status-publish","format-standard","hentry","category-tree","tag-map","tag-medium","tag-set","tag-traversal","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4772","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4772"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4772\/revisions"}],"predecessor-version":[{"id":9075,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4772\/revisions\/9075"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4772"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4772"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4772"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}