{"id":2228,"date":"2018-03-19T20:57:05","date_gmt":"2018-03-20T03:57:05","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2228"},"modified":"2018-03-19T20:58:38","modified_gmt":"2018-03-20T03:58:38","slug":"leetcode-623-add-one-row-to-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-623-add-one-row-to-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 623. Add One Row to Tree"},"content":{"rendered":"

\u9898\u76ee\u5927\u610f\uff1a\u5728\u6811\u7684\u6240\u6709\u7b2cd\u5c42\u4f4d\u7f6e\u63d2\u5165\u5143\u7d20v\u3002<\/p>\n

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

https:\/\/leetcode.com\/problems\/add-one-row-to-tree\/description\/<\/a><\/p>\n

Given the root of a binary tree, then value\u00a0v<\/code>\u00a0and depth\u00a0d<\/code>, you need to add a row of nodes with value\u00a0v<\/code>\u00a0at the given depth\u00a0d<\/code>. The root node is at depth 1.<\/p>\n

The adding rule is: given a positive integer depth\u00a0d<\/code>, for each NOT null tree nodes\u00a0N<\/code>\u00a0in depth\u00a0d-1<\/code>, create two tree nodes with value\u00a0v<\/code>\u00a0as\u00a0N's<\/code>\u00a0left subtree root and right subtree root. And\u00a0N's<\/code>\u00a0original left subtree<\/b>\u00a0should be the left subtree of the new left subtree root, its\u00a0original right subtree<\/b>\u00a0should be the right subtree of the new right subtree root. If depth\u00a0d<\/code>\u00a0is 1 that means there is no depth d-1 at all, then create a tree node with value\u00a0v<\/b>\u00a0as the new root of the whole original tree, and the original tree is the new root’s left subtree.<\/p>\n

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

Input:<\/b> \r\nA binary tree as following:\r\n       4\r\n     \/   \\\r\n    2     6\r\n   \/ \\   \/ \r\n  3   1 5   \r\n\r\nv = 1<\/b>\r\n\r\nd = 2<\/b>\r\n\r\nOutput:<\/b> \r\n       4\r\n      \/ \\\r\n     1   1\r\n    \/     \\\r\n   2       6\r\n  \/ \\     \/ \r\n 3   1   5   \r\n\r\n<\/pre>\n
Example 2:<\/b><\/p>\n
Input:<\/b> \r\nA binary tree as following:\r\n      4\r\n     \/   \r\n    2    \r\n   \/ \\   \r\n  3   1    \r\n\r\nv = 1<\/b>\r\n\r\nd = 3<\/b>\r\n\r\nOutput:<\/b> \r\n      4\r\n     \/   \r\n    2\r\n   \/ \\    \r\n  1   1\r\n \/     \\  \r\n3       1\r\n<\/pre>\n
Note:<\/b><\/p>\n
    \n
  1. The given d is in range [1, maximum depth of the given tree + 1].<\/li>\n
  2. The given binary tree has at least one tree node.<\/li>\n<\/ol>\n
    Solution: Recursion<\/strong><\/h1>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 19 ms (beats 90.85%)\r\nclass Solution {\r\npublic:\r\n  TreeNode* addOneRow(TreeNode* root, int v, int d) {\r\n    if (root == nullptr) return nullptr;\r\n    \r\n    \/\/ Special case.\r\n    if (d == 1) {\r\n      TreeNode* new_root = new TreeNode(v);\r\n      new_root->left = root;\r\n      return new_root;\r\n    }\r\n    \r\n    if (d == 2) {\r\n      TreeNode* l = root->left;\r\n      root->left = new TreeNode(v);\r\n      root->left->left = l;\r\n      \r\n      TreeNode* r = root->right;\r\n      root->right = new TreeNode(v);\r\n      root->right->right = r;\r\n    } else {\r\n      addOneRow(root->left, v, d - 1);\r\n      addOneRow(root->right, v, d - 1);\r\n    }\r\n    \r\n    return root;\r\n  }\r\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    \u9898\u76ee\u5927\u610f\uff1a\u5728\u6811\u7684\u6240\u6709\u7b2cd\u5c42\u4f4d\u7f6e\u63d2\u5165\u5143\u7d20v\u3002 Problem https:\/\/leetcode.com\/problems\/add-one-row-to-tree\/description\/ Given the root of a binary tree, then value\u00a0v\u00a0and depth\u00a0d, you need to add a row of nodes with value\u00a0v\u00a0at the given…<\/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":[177,263,17,28],"class_list":["post-2228","post","type-post","status-publish","format-standard","hentry","category-tree","tag-medium","tag-pointers","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2228","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=2228"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2228\/revisions"}],"predecessor-version":[{"id":2231,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2228\/revisions\/2231"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2228"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}