{"id":1117,"date":"2021-04-11T16:47:08","date_gmt":"2021-04-11T08:47:08","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=1117"},"modified":"2021-04-11T17:01:02","modified_gmt":"2021-04-11T09:01:02","slug":"leetcode-1302","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/04\/11\/leetcode-1302\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 1302 \u2013 Deepest Leaves Sum"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"1117\" class=\"elementor elementor-1117\">\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-2322fac elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2322fac\" 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-ee2bb19\" data-id=\"ee2bb19\" 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-cdc49e6 elementor-widget elementor-widget-text-editor\" data-id=\"cdc49e6\" 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 the <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>root<\/code><\/span><span class=\"md-plain\"> of a binary tree, return <\/span><span class=\"md-pair-s \"><em><span class=\"md-plain\">the sum of values of its deepest leaves<\/span><\/em><\/span><span class=\"md-plain\">.<\/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\/2019\/07\/31\/1483_ex1.png\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/07\/31\/1483_ex1.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,2,3,4,5,null,6,7,null,null,null,null,8]<\/span><br \/><span role=\"presentation\">Output: 15<\/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><pre class=\"md-fences md-end-block ty-contain-cm modeLoaded\" lang=\"\" spellcheck=\"false\"><span role=\"presentation\">Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]<\/span><br \/><span role=\"presentation\">Output: 19<\/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 number of nodes in the tree is in the range <\/span><span class=\"md-pair-s\" spellcheck=\"false\"><code>[1, 104]<\/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-pair-s\" spellcheck=\"false\"><code>1 &lt;= Node.val &lt;= 100<\/code><\/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-9c60b08 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9c60b08\" 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-089784b\" data-id=\"089784b\" 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-384ce89 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"384ce89\" 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-61adec4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"61adec4\" 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-94fe2b9\" data-id=\"94fe2b9\" 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-01bdb72 elementor-widget elementor-widget-text-editor\" data-id=\"01bdb72\" 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\uff08\u5169\u6b21DFS\uff09\uff1a<\/strong><\/span><\/h4><p>\u00a0 \u00a0 \u00a0 \u00a0\u9019\u984c\u7d66\u6211\u5011\u4e00\u500b\u4e8c\u53c9\u6a39\uff0c\u7136\u5f8c\u9700\u8981\u6211\u5011\u5f97\u51fa\u9019\u500b\u4e8c\u53c9\u6a39\u4e2d\uff0c\u6700\u6df1\u7684\u8449\u7bc0\u9ede\u7684\u503c\u7684\u7e3d\u548c\u3002\u6700\u76f4\u63a5\uff0c\u4e5f\u662f\u4f5c\u8005\u7d66\u51fa\u7684\u63d0\u793a\u601d\u8def\u5c31\u662f\u5c0d\u6a39\u9032\u884c\u5169\u6b21\u904d\u6b77\u3002<span style=\"color: #ff0000;\">\u7b2c\u4e00\u6b21\u904d\u6b77\u5f97\u51fa\u6a39\u7684\u6df1\u5ea6\uff1b\u7b2c\u4e8c\u6b21\u904d\u6b77\u518d\u6839\u64da\u9019\u500b\u6df1\u5ea6\u7684\u57fa\u790e\u4e0a\uff0c\u627e\u5230\u6700\u6df1\u7684\u7bc0\u9ede\uff0c\u4e26\u5c07\u5b83\u5011\u7684\u503c\u52a0\u8d77\u4f86\u3002<\/span><\/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-9290012 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9290012\" 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-8467b02\" data-id=\"8467b02\" 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-00cba35 elementor-widget elementor-widget-text-editor\" data-id=\"00cba35\" 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> { \u00a0 \u00a0<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-keyword\">public<\/span> <span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">DeepestLeavesSum<\/span>(<span class=\"cm-variable\">TreeNode<\/span> <span class=\"cm-variable\">root<\/span>) {<\/span><br \/><span role=\"presentation\">        \/\/\u7b2c\u4e00\u6b21DFS\u5f97\u51fa\u6700\u5927\u6df1\u5ea6<br \/> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">depth<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">DepthFinder<\/span>(<span class=\"cm-variable\">root<\/span>);<br \/><\/span>        \/\/\u7b2c\u4e8c\u6b21DFS\u6839\u64da\u6df1\u5ea6\u627e\u5230\u6700\u6df1\u7684\u8449\u7bc0\u9ede\u4e26\u8a08\u7b97\u7e3d\u548c<br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">sum<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">SumFinder<\/span>(<span class=\"cm-variable\">root<\/span>, <span class=\"cm-variable\">depth<\/span>); \u00a0 \u00a0 \u00a0 \u00a0<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">return<\/span> <span class=\"cm-variable\">sum<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0  }<br \/><\/span>    \/\/\u6df1\u5ea6<br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">DepthFinder<\/span>(<span class=\"cm-variable\">TreeNode<\/span> <span class=\"cm-variable\">node<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span>(<span class=\"cm-variable\">node<\/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\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">depth<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-number\">1<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">leftDepth<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">DepthFinder<\/span>(<span class=\"cm-variable\">node<\/span>.<span class=\"cm-variable\">left<\/span>);<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">rightDepth<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">DepthFinder<\/span>(<span class=\"cm-variable\">node<\/span>.<span class=\"cm-variable\">right<\/span>);<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-variable\">depth<\/span> <span class=\"cm-operator\">=<\/span> <span class=\"cm-variable\">depth<\/span> <span class=\"cm-operator\">+<\/span> <span class=\"cm-variable\">Math<\/span>.<span class=\"cm-variable\">Max<\/span>(<span class=\"cm-variable\">leftDepth<\/span>, <span class=\"cm-variable\">rightDepth<\/span>);<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">return<\/span> <span class=\"cm-variable\">depth<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0  }<br \/><\/span>    \/\/\u5f97\u5230\u6700\u6df1\u7bc0\u9ede\u7684\u503c<br \/><span role=\"presentation\"> \u00a0 \u00a0<span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">SumFinder<\/span>(<span class=\"cm-variable\">TreeNode<\/span> <span class=\"cm-variable\">node<\/span>, <span class=\"cm-variable-3\">int<\/span> <span class=\"cm-variable\">depth<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span>(<span class=\"cm-variable\">node<\/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\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">if<\/span>(<span class=\"cm-variable\">depth<\/span> <span class=\"cm-operator\">==<\/span> <span class=\"cm-number\">1<\/span> <span class=\"cm-operator\">&amp;&amp;<\/span> <span class=\"cm-variable\">node<\/span> <span class=\"cm-operator\">!=<\/span> <span class=\"cm-atom\">null<\/span>)<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  {<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">return<\/span> <span class=\"cm-variable\">node<\/span>.<span class=\"cm-variable\">val<\/span>;<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0  }<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<\/span><br \/><span role=\"presentation\"> \u00a0 \u00a0 \u00a0 \u00a0<span class=\"cm-keyword\">return<\/span> <span class=\"cm-variable\">SumFinder<\/span>(<span class=\"cm-variable\">node<\/span>.<span class=\"cm-variable\">left<\/span>, <span class=\"cm-variable\">depth<\/span> <span class=\"cm-operator\">-<\/span> <span class=\"cm-number\">1<\/span>) <span class=\"cm-operator\">+<\/span> <span class=\"cm-variable\">SumFinder<\/span>(<span class=\"cm-variable\">node<\/span>.<span class=\"cm-variable\">right<\/span>, <span class=\"cm-variable\">depth<\/span> <span class=\"cm-operator\">-<\/span> <span class=\"cm-number\">1<\/span>);<\/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 the root of a binary tree, return the sum o &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"\" href=\"https:\/\/lonelinerd.com\/index.php\/2021\/04\/11\/leetcode-1302\/\"> <span class=\"screen-reader-text\">[LeetCode\u5237\u984c\u7b46\u8a18] 1302 \u2013 Deepest Leaves Sum<\/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-1117","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\/1117","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=1117"}],"version-history":[{"count":8,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/1117\/revisions"}],"predecessor-version":[{"id":1126,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/1117\/revisions\/1126"}],"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=1117"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=1117"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=1117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}