{"id":3801,"date":"2018-09-01T22:42:34","date_gmt":"2018-09-02T05:42:34","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3801"},"modified":"2020-02-11T22:50:17","modified_gmt":"2020-02-12T06:50:17","slug":"leetcode-897-increasing-order-search-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-897-increasing-order-search-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 897. Increasing Order Search Tree"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given a tree, rearrange the tree in\u00a0in-order<\/strong>\u00a0so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.<\/p>\n

Example 1:<\/strong>\nInput:<\/strong> [5,3,6,2,4,null,8,1,null,null,null,7,9]\n\n       5\n      \/ \\\n    3    6\n   \/ \\    \\\n  2   4    8\n\u00a0\/        \/ \\ \n1        7   9\n\nOutput:<\/strong> [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]\n\n 1\n\u00a0 \\\n\u00a0  2\n\u00a0   \\\n\u00a0    3\n\u00a0     \\\n\u00a0      4\n\u00a0       \\\n\u00a0        5\n\u00a0         \\\n\u00a0          6\n\u00a0           \\\n\u00a0            7\n\u00a0             \\\n\u00a0              8\n\u00a0               \\\n                 9<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. The number of nodes in the given tree will be between 1 and 100.<\/li>\n
  2. Each node will have a unique integer value from 0 to 1000.<\/li>\n<\/ol>\n
    Solution: In-order traversal<\/strong><\/h1>\n
    root = 5<\/div>\n
    inorder(root.left) \u4e4b\u540e<\/div>\n
    self.prev = 4<\/div>\n
    \uff081-4\uff09\u5df2\u7ecf\u5904\u7406\u5b8c\u4e86\uff0c\u8fd9\u65f6\u5019\u7684\u6811\u662f\u5f88\u5947\u602a\u7684\u4e00\u4e2a\u5f62\u72b6\uff0c3\u5373\u662f2\u7684\u53f3\u5b50\u6811\uff0c\u53c8\u662f5\u7684\u5de6\u5b50\u6811\u3002<\/div>\n
    \u00a0 \u00a01
    \n<\/span><\/div>\n
    \n
    \u00a0 \u00a0 \\<\/span><\/div>\n
    \u00a0 \u00a0 \u00a02\u00a0 \u00a0 5<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \\\u00a0 \/\u00a0 \\\u00a0<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a03\u00a0 \u00a0 \u00a06<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \\\u00a0 \u00a0 \u00a0\\<\/span><\/div>\n
    \u00a0prev -><\/span><\/b>\u00a04<\/span><\/b>\u00a0 \u00a0 \u00a08<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\u00a0 \\<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 7\u00a0 \u00a0 9<\/span><\/div>\n
    —————————<\/div>\n
    <\/div>\n<\/div>\n
    5.left = None # \u628a5->3\u7684\u94fe\u63a5\u65ad\u5f00<\/div>\n
    5<\/span><\/div>\n
    \u00a0\\<\/span><\/div>\n
    \u00a0 6<\/span><\/div>\n
    \u00a0 \u00a0\\<\/span><\/div>\n
    \u00a0 \u00a0 8<\/span><\/div>\n
    \u00a0 \u00a0\/\u00a0 \\<\/span><\/div>\n
    \u00a0 7\u00a0 \u00a0 9<\/span><\/div>\n
    —————————–<\/div>\n
    self.prev.right = root\u00a0 <=> 4.right = 5<\/div>\n
    \u628a5\u63a5\u52304\u7684\u53f3\u5b50\u6811<\/div>\n
    1<\/span><\/div>\n
    \u00a0\\<\/span><\/div>\n
    \u00a0 2<\/span><\/div>\n
    \u00a0 \u00a0\\<\/span><\/div>\n
    \u00a0 \u00a0 3<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0\\<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 4<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0\\<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0\u00a05 <– prev<\/b><\/span><\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\\<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a06<\/span><\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\\<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 8<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \/\u00a0 \u00a0\\<\/span><\/div>\n
    \u00a0 \u00a0 \u00a0 \u00a0 \u00a07\u00a0 \u00a0 \u00a09<\/span><\/div>\n
    self.prev = root <=> prev = 5<\/span><\/div>\n
    inorder(5.right) <=> inorder(6) \u7136\u540e\u518d\u53bb\u9012\u5f52\u5904\u74066\uff08\u53ca\u5176\u5b50\u6811\uff09\u5373\u53ef\u3002<\/div>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\n\/\/ Running time: 64 ms\nclass Solution {\npublic:\n  TreeNode* increasingBST(TreeNode* root) {\n    TreeNode dummy(0);\n    prev_ = &dummy;\n    inorder(root);\n    return dummy.right;\n  }\nprivate:  \n  TreeNode* prev_;\n  void inorder(TreeNode* root) {\n    if (root == nullptr) return;\n    inorder(root->left);\n    prev_->right = root;  \n    prev_ = root;\n    prev_->left = nullptr;\n    inorder(root->right);\n  }\n};<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    class Solution {\n  private TreeNode prev;\n  \n  public TreeNode increasingBST(TreeNode root) {\n    TreeNode dummy = new TreeNode(0);\n    this.prev = dummy;\n    inorder(root);\n    return dummy.right;\n  }\n  \n  private void inorder(TreeNode root) {\n    if (root == null) return;\n    inorder(root.left);\n    this.prev.right = root;\n    this.prev = root;\n    this.prev.left = null;\n    inorder(root.right);\n  }\n}<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    class Solution:\n  def increasingBST(self, root):\n    dummy = TreeNode(0)\n    self.prev = dummy\n    def inorder(root):\n      if not root: return None\n      inorder(root.left)\n      root.left = None\n      self.prev.right = root\n      self.prev = root\n      inorder(root.right)\n    inorder(root)\n    return dummy.right<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Given a tree, rearrange the tree in\u00a0in-order\u00a0so that the leftmost node in the tree is now the root of the tree, and every node…<\/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":[58,392,28],"class_list":["post-3801","post","type-post","status-publish","format-standard","hentry","category-tree","tag-inorder","tag-modify","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3801","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=3801"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3801\/revisions"}],"predecessor-version":[{"id":6300,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3801\/revisions\/6300"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3801"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3801"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3801"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}