{"id":898,"date":"2021-03-09T21:21:05","date_gmt":"2021-03-09T13:21:05","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=898"},"modified":"2021-03-09T21:38:46","modified_gmt":"2021-03-09T13:38:46","slug":"leetcode-623","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/03\/09\/leetcode-623\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 623 – Add One Row to Tree"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t

\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/span><\/h4>

Given the root of a binary tree, then value <\/span>v<\/code><\/span> and depth <\/span>d<\/code><\/span>, you need to add a row of nodes with value <\/span>v<\/code><\/span> at the given depth <\/span>d<\/code><\/span>. The root node is at depth 1.<\/span><\/p>

The adding rule is: given a positive integer depth <\/span>d<\/code><\/span>, for each NOT null tree nodes <\/span>N<\/code><\/span> in depth <\/span>d-1<\/code><\/span>, create two tree nodes with value <\/span>v<\/code><\/span> as <\/span>N's<\/code><\/span> left subtree root and right subtree root. And <\/span>N's<\/code><\/span> original left subtree<\/span><\/strong><\/span> should be the left subtree of the new left subtree root, its <\/span>original right subtree<\/span><\/strong><\/span> should be the right subtree of the new right subtree root. If depth <\/span>d<\/code><\/span> is 1 that means there is no depth d-1 at all, then create a tree node with value <\/span>v<\/span><\/strong><\/span> as the new root of the whole original tree, and the original tree is the new root’s left subtree.<\/span><\/p>

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

Input: <\/span>
A binary tree as following:<\/span>
 \u00a0 \u00a0 \u00a0 4<\/span>
 \u00a0 \u00a0 \/ \u00a0 \\<\/span>
 \u00a0  2 \u00a0 \u00a0 6<\/span>
 \u00a0 \/ \\ \u00a0 \/ <\/span>
  3 \u00a0 1 5 \u00a0 <\/span>
\u200b<\/span>
v = 1<\/span>
\u200b<\/span>
d = 2<\/span>
\u200b<\/span>
Output: <\/span>
 \u00a0 \u00a0 \u00a0 4<\/span>
 \u00a0 \u00a0  \/ \\<\/span>
 \u00a0 \u00a0 1 \u00a0 1<\/span>
 \u00a0  \/ \u00a0 \u00a0 \\<\/span>
 \u00a0 2 \u00a0 \u00a0 \u00a0 6<\/span>
  \/ \\ \u00a0 \u00a0 \/ <\/span>
 3 \u00a0 1 \u00a0 5 \u00a0 <\/span><\/pre>
\u00a0<\/p>
Example 2:<\/span><\/strong><\/span><\/p>
Input: <\/span>
A binary tree as following:<\/span>
 \u00a0 \u00a0  4<\/span>
 \u00a0 \u00a0 \/ \u00a0 <\/span>
 \u00a0  2 \u00a0 \u00a0<\/span>
 \u00a0 \/ \\ \u00a0 <\/span>
  3 \u00a0 1 \u00a0 \u00a0<\/span>
\u200b<\/span>
v = 1<\/span>
\u200b<\/span>
d = 3<\/span>
\u200b<\/span>
Output: <\/span>
 \u00a0 \u00a0  4<\/span>
 \u00a0 \u00a0 \/ \u00a0 <\/span>
 \u00a0  2<\/span>
 \u00a0 \/ \\ \u00a0 \u00a0<\/span>
  1 \u00a0 1<\/span>
 \/ \u00a0 \u00a0 \\ \u00a0<\/span>
3 \u00a0 \u00a0 \u00a0 1<\/span><\/pre>
\u00a0<\/p>
Note:<\/span><\/strong><\/span><\/p>
  1. The given d is in range [1, maximum depth of the given tree + 1].<\/span><\/p><\/li>
  2. The given binary tree has at least one tree node.<\/span><\/p><\/li><\/ol>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t
    \u4e00\u5237\u984c\u89e3\uff08Recursion\uff09\uff1a<\/strong><\/span><\/h4>
    \u00a0 \u00a0 \u00a0 \u9019\u984c\u8981\u6211\u5011\u5728\u4e00\u500b\u4e8c\u53c9\u6a39\u4e2d\u7684\u67d0\u4e00\u5c64(d)\uff0c\u63d2\u5165\u4e00\u5c64\u503c\u70ba(v)\u7684\u7bc0\u9ede\uff0c\u7136\u5f8c\u5c07\u539f\u4f86\u4e0b\u4e00\u5c64\u7684\u5de6\u5b50\u7bc0\u9ede\u8b8a\u6210\u63d2\u9032\u4f86\u7684\u9019\u4e00\u5c64\u7684\u5de6\u5b50\u7bc0\u9ede\uff0c\u53f3\u5b50\u7bc0\u9ede\u4e5f\u4e00\u6a23\u3002<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u96d6\u7136\u9019\u984c\u6a19\u70baMedium\uff0c\u4f46\u662f\u89e3\u984c\u601d\u8def\u5f88\u7c21\u55ae\uff0c\u4e00\u770b\u5c31\u77e5\u9053\u53ef\u4ee5\u7528DFS\u4f86\u505a\u3002\u76f4\u63a5\u5229\u7528\u905e\u6b78\uff0c\u5f9e\u6a39\u7684\u9802\u90e8\u5411\u5176\u5de6\u53f3\u5b50\u7bc0\u9ede\u79fb\u52d5\uff0c\u4e26\u8a18\u9304\u7576\u524d\u5c64\u6578\u6df1\u5ea6\u3002\u7576\u6df1\u5ea6\u7b49\u65bc\u63d2\u5165\u76ee\u6a19\u5c64\u6578 – 1\u6642\uff0c\u4ee3\u8868\u7576\u524d\u7bc0\u9ede\u7684\u4e0b\u4e00\u5c64\u5c31\u662f\u8981\u63d2\u5165\u7684\u5c64\u6578\u3002<\/p>
    \u00a0 \u00a0 \u00a0 \u00a0 \u56e0\u6b64\uff0c\u6211\u5011\u5728\u7576\u524d\u5c64\u505c\u4e0b\u4f86\uff0c\u5148\u8072\u660e\u4e00\u500bTreeNode\u4fdd\u5728\u7576\u524d\u5c64\u5b50\u7bc0\u9ede\u7684\u5f15\u7528\uff0c\u4ee5\u514d\u4e1f\u5931\uff0c\u7136\u5f8c\u628a\u7576\u524d\u7bc0\u9ede\u7684\u5b50\u7bc0\u9ede\u6307\u5411\u4ee5\u63d2\u5165\u503c\u9032\u884c\u521d\u59cb\u5316\u7684\u7bc0\u9ede\uff08new TreeNode(addVal))\uff0c\u6700\u5f8c\u518d\u628a\u525b\u525b\u4fdd\u5b58\u4e0b\u4f86\u7684\u820a\u5b50\u7bc0\u9ede\u8b8a\u6210\u63d2\u5165\u7bc0\u9ede\u7684\u5b50\u7bc0\u9ede\uff08node.left.left = currNext\uff09\uff0c\u5b8c\u6210\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t
    \n\t\t\t
    \n\t\t\t\t\t\t\t
    \n\t\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t
    \n\t\t\t\t
    public<\/span> class<\/span> Solution<\/span> {<\/span>
     \u00a0 \u00a0public<\/span> TreeNode<\/span> AddOneRow<\/span>(TreeNode<\/span> root<\/span>, int<\/span> v<\/span>, int<\/span> d<\/span>) {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0\/\/Add in first stair<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(d<\/span> ==<\/span> 1<\/span>)<\/span>
     \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0TreeNode<\/span> newHead<\/span> =<\/span> new<\/span> TreeNode<\/span>(v<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0newHead<\/span>.left<\/span> =<\/span> root<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0return<\/span> newHead<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0RowAdder<\/span>(root<\/span>, v<\/span>, d<\/span>, 1<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0return<\/span> root<\/span>;<\/span>
     \u00a0  }<\/span>
     \u00a0 \u00a0<\/span>
     \u00a0 \u00a0void<\/span> RowAdder<\/span>(TreeNode<\/span> node<\/span>, int<\/span> addVal<\/span>, int<\/span> targetStair<\/span>, int<\/span> currDepth<\/span>)<\/span>
     \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(node<\/span> ==<\/span> null<\/span>) { return<\/span>; }
    <\/span>
            \/\/if currDepth = targetStair - 1
            \/\/means next stair should be new Node(addVal);<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(currDepth<\/span> ==<\/span> targetStair<\/span> -<\/span> 1<\/span>)<\/span>
     \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/Insert addVal Node between currNode and currNode.next
                \/\/Save curr next node first;<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0TreeNode<\/span> currNext<\/span> =<\/span> node<\/span>.left<\/span>;
    <\/span>            \/\/Add addVal in next node
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0node<\/span>.left<\/span> =<\/span> new<\/span> TreeNode<\/span>(addVal<\/span>);
                \/\/Set next Node(addVal)'s next node be currNext<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0node<\/span>.left<\/span>.left<\/span> =<\/span> currNext<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0
    <\/span>            \/\/So be it in RightSide
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0currNext<\/span> =<\/span> node<\/span>.right<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0node<\/span>.right<\/span> =<\/span> new<\/span> TreeNode<\/span>(addVal<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0node<\/span>.right<\/span>.right<\/span> =<\/span> currNext<\/span>;<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0else<\/span><\/span>
     \u00a0 \u00a0 \u00a0  {<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\/\/DFS<\/span><\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0RowAdder<\/span>(node<\/span>.left<\/span>, addVal<\/span>, targetStair<\/span>, currDepth<\/span> +<\/span> 1<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0RowAdder<\/span>(node<\/span>.right<\/span>, addVal<\/span>, targetStair<\/span>, currDepth<\/span> +<\/span> 1<\/span>);<\/span>
     \u00a0 \u00a0 \u00a0  }<\/span>
     \u00a0  }<\/span>
    }<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"
    \u984c\u76ee\u63cf\u8ff0\uff1a Given the root of a binary tree, then value v and …<\/p>\n
      [LeetCode\u5237\u984c\u7b46\u8a18] 623 – Add One Row to Tree<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":570,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,16],"tags":[],"class_list":["post-898","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming-notes","category-leetcodes"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/lonelinerd.com\/wp-content\/uploads\/2021\/02\/FeatureCover_LeetCoding.png","_links":{"self":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/898","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/comments?post=898"}],"version-history":[{"count":14,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/898\/revisions"}],"predecessor-version":[{"id":912,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/898\/revisions\/912"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media\/570"}],"wp:attachment":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media?parent=898"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=898"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=898"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}