{"id":794,"date":"2021-03-01T14:09:18","date_gmt":"2021-03-01T06:09:18","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=794"},"modified":"2021-03-01T14:50:23","modified_gmt":"2021-03-01T06:50:23","slug":"leetcode-559","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/03\/01\/leetcode-559\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 559 &#8211; Maximum Depth of N-ary Tree"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"794\" class=\"elementor elementor-794\">\n\t\t\t\t\t\t<div class=\"elementor-inner\">\n\t\t\t\t<div class=\"elementor-section-wrap\">\n\t\t\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7cb2643 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7cb2643\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t\t\t<div class=\"elementor-row\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-28a7f10\" data-id=\"28a7f10\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-column-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t<div class=\"elementor-widget-wrap\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-242ae2e elementor-widget elementor-widget-text-editor\" data-id=\"242ae2e\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-text-editor elementor-clearfix\">\n\t\t\t\t<h4><span style=\"text-decoration: underline;\"><strong>\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/span><\/h4><p class=\"md-end-block md-p\"><span class=\"md-plain\">Given a n-ary tree, find its maximum depth.<\/span><\/p><p class=\"md-end-block md-p\"><span class=\"md-plain\">The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.<\/span><\/p><p class=\"md-end-block md-p\"><span class=\"md-pair-s \"><em><span class=\"md-plain\">Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).<\/span><\/em><\/span><\/p><p class=\"md-end-block md-p\">\u00a0<\/p><p class=\"md-end-block md-p\"><span class=\"md-pair-s \"><strong><span class=\"md-plain\">Example 1:<\/span><\/strong><\/span><\/p><p class=\"md-end-block md-p\"><span class=\"md-image md-img-loaded\" data-src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/10\/12\/narytreeexample.png\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/10\/12\/narytreeexample.png\" alt=\"img\" \/><\/span><\/p><pre class=\"md-fences md-end-block ty-contain-cm modeLoaded\" lang=\"\" spellcheck=\"false\"><span role=\"presentation\">Input: root = [1,null,3,2,4,null,5,6]<\/span><br \/><span role=\"presentation\">Output: 3<\/span><\/pre><p class=\"md-end-block md-p\"><span class=\"md-pair-s \"><strong><span class=\"md-plain\">Example 2:<\/span><\/strong><\/span><\/p><p class=\"md-end-block md-p\"><span class=\"md-image md-img-loaded\" data-src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/11\/08\/sample_4_964.png\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/11\/08\/sample_4_964.png\" alt=\"img\" \/><\/span><\/p><pre class=\"md-fences md-end-block ty-contain-cm modeLoaded\" lang=\"\" spellcheck=\"false\"><span role=\"presentation\">Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]<\/span><br \/><span role=\"presentation\">Output: 5<\/span><\/pre><p class=\"md-end-block md-p\">\u00a0<\/p><p class=\"md-end-block md-p\"><span class=\"md-pair-s \"><strong><span class=\"md-plain\">Constraints:<\/span><\/strong><\/span><\/p><ul class=\"ul-list\" data-mark=\"-\"><li class=\"md-list-item\"><p class=\"md-end-block md-p\"><span class=\"md-plain\">The depth of the n-ary tree is less than or equal to <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>1000<\/code><\/span><span class=\"md-plain\">.<\/span><\/p><\/li><li class=\"md-list-item md-focus-container\"><p class=\"md-end-block md-p md-focus\"><span class=\"md-plain\">The total number of nodes is between <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>[0, 104]<\/code><\/span><span class=\"md-plain\">.<\/span><\/p><\/li><\/ul>\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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0469f93 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0469f93\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t\t\t<div class=\"elementor-row\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-db78cda\" data-id=\"db78cda\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-column-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t<div class=\"elementor-widget-wrap\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1768bb9 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"1768bb9\" data-element_type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-71f4837 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"71f4837\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t\t\t<div class=\"elementor-row\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3125e06\" data-id=\"3125e06\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-column-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t<div class=\"elementor-widget-wrap\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-25c952c elementor-widget elementor-widget-text-editor\" data-id=\"25c952c\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-text-editor elementor-clearfix\">\n\t\t\t\t<h4><span style=\"text-decoration: underline;\"><strong>\u4e00\u5237\u984c\u89e3\uff08Bottom-up Recursion\uff09\uff1a<\/strong><\/span><\/h4><p>\u00a0 \u00a0 \u00a0 \u00a0 \u9019\u984c\u9700\u8981\u627e\u5230\u4e00\u500bN\u53c9\u6a39\u4e2d\u7684\u6700\u5927\u6df1\u5ea6\uff0c\u6211\u5011\u53ef\u4ee5\u901a\u904eBotton-up\u7684Recursion\u4f86\u89e3\u6c7a\u3002\u53ea\u8981\u7576\u524d\u7bc0\u9ede\u4e0d\u70ba\u7a7a\uff0c\u5c31\u9ed8\u8a8d\u6709\u300c\u4e00\u5c64\u300d\u7684\u5b58\u5728\uff08curr = 1\uff09\u3002\u7136\u5f8c\u5617\u8a66\u904d\u6b77\u7576\u524d\u7bc0\u9ede\u4e0b\u7684\u6240\u6709\u5b50\u7bc0\u9ede\uff0c\u518d\u5c0d\u5b50\u7bc0\u9ede\u9032\u884c\u8abf\u7528MaxDepth\uff0c\u4e00\u76f4\u8abf\u7528\u76f4\u5230\u518d\u6c92\u6709\u5b50\u7bc0\u9ede\uff08root == null\uff09\u3002\u6bcf\u6b21\u8abf\u7528\u7684\u6210\u529f\uff0c\u90fd\u6703\u4f7f\u8a72\u7bc0\u9ede\u7684maxDepth\u8a18\u9304\u503c+1\uff0c\u7576\u63a5\u89f8\u5230N\u53c9\u6a39\u7684\u5e95\u90e8\u5f8c\uff0c\u8a18\u9304\u5b8c\u6210\u7684maxDepth\u6703\u4e00\u5c64\u4e00\u5c64\u8fd4\u56de\uff0c\u6bcf\u6b21\u8fd4\u56de\u6211\u5011\u90fd\u5c0d\u4e0d\u540c\u5206\u652f\u8fd4\u56de\u7684maxDepth\u9032\u884c\u53d6\u6700\u5927\u503c\uff0c\u4e26\u52a0\u4e0a\u7576\u524d\u5c64\u76841\uff08curr + maxDepth\uff09\uff0c\u6700\u5f8c\u5c31\u53ef\u4ee5\u9019\u500bN\u53c9\u6a39\u7684\u6700\u5927\u6df1\u5ea6\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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-70c7da6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"70c7da6\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t\t\t<div class=\"elementor-row\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-da14870\" data-id=\"da14870\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-column-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t<div class=\"elementor-widget-wrap\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-aaa0ff8 elementor-widget elementor-widget-text-editor\" data-id=\"aaa0ff8\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-text-editor elementor-clearfix\">\n\t\t\t\t<pre class=\"md-fences md-end-block ty-contain-cm modeLoaded\" lang=\"c#\" spellcheck=\"false\"><span role=\"presentation\"><span class=\"cm-keyword\">public<\/span> <span class=\"cm-keyword\">class<\/span> <span class=\"cm-def\">Solution<\/span> {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">public<\/span> <span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">MaxDepth<\/span>(<span class=\"cm-variable\">Node<\/span> <span class=\"cm-variable\">root<\/span>) {<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span>(<span class=\"cm-variable\">root<\/span> <span class=\"cm-operator\">==<\/span> <span class=\"cm-atom\">null<\/span>) { <span class=\"cm-keyword\">return<\/span> <span class=\"cm-number\">0<\/span>; }<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">curr<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-number\">1<\/span>;<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">maxDepth<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-number\">0<\/span>; \u00a0 \u00a0<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">for<\/span> (<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">i<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-number\">0<\/span>; <span class=\"cm-variable\">i<\/span> <span class=\"cm-operator\">&lt;<\/span> <span class=\"cm-variable\">root<\/span>.<span class=\"cm-variable\">children<\/span>.<span class=\"cm-variable\">Count<\/span>; <span class=\"cm-variable\">i<\/span><span class=\"cm-operator\">++<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  {<br \/><\/span>            \/\/\u5728\u4e0d\u540c\u5206\u652f\u4e2d\uff0c\u53d6\u6df1\u5ea6\u6700\u5927\u7684\u4e00\u652f\u7684\u6df1\u5ea6\u503c<br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">downStair<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">MaxDepth<\/span>(<span class=\"cm-variable\">root<\/span>.<span class=\"cm-variable\">children<\/span>[<span class=\"cm-variable\">i<\/span>]);<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">maxDepth<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">Math<\/span>.<span class=\"cm-variable\">Max<\/span>(<span class=\"cm-variable\">maxDepth<\/span>, <span class=\"cm-variable\">downStair<\/span>);<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  }<\/span><br \/><span role=\"presentation\">\u200b<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">return<\/span> <span class=\"cm-variable\">curr<\/span> <span class=\"cm-operator\">+<\/span> <span class=\"cm-variable\">maxDepth<\/span>; \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<\/span><br \/><span role=\"presentation\"> \u00a0  }<\/span><br \/><span role=\"presentation\">}<\/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":"<p>\u984c\u76ee\u63cf\u8ff0\uff1a Given a n-ary tree, find its maximum depth. The m &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"\" href=\"https:\/\/lonelinerd.com\/index.php\/2021\/03\/01\/leetcode-559\/\"> <span class=\"screen-reader-text\">[LeetCode\u5237\u984c\u7b46\u8a18] 559 &#8211; Maximum Depth of N-ary Tree<\/span> Read More &raquo;<\/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-794","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\/794","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=794"}],"version-history":[{"count":26,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/794\/revisions"}],"predecessor-version":[{"id":821,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/794\/revisions\/821"}],"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=794"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=794"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=794"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}