{"id":5738,"date":"2019-10-09T21:11:08","date_gmt":"2019-10-10T04:11:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5738"},"modified":"2019-10-09T21:13:37","modified_gmt":"2019-10-10T04:13:37","slug":"leetcode-129-sum-root-to-leaf-numbers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-129-sum-root-to-leaf-numbers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 129. Sum Root to Leaf Numbers"},"content":{"rendered":"\n

Given a binary tree containing digits from 0-9<\/code> only, each root-to-leaf path could represent a number.<\/p>\n\n\n\n

An example is the root-to-leaf path 1->2->3<\/code> which represents the number 123<\/code>.<\/p>\n\n\n\n

Find the total sum of all root-to-leaf numbers.<\/p>\n\n\n\n

Note:<\/strong> A leaf is a node with no children.<\/p>\n\n\n\n

Example:<\/strong><\/p>\n\n\n\n

Input:<\/strong> [1,2,3]\n    1\n   \/ \\\n  2   3\nOutput:<\/strong> 25\nExplanation:<\/strong>\nThe root-to-leaf path 1->2<\/code> represents the number 12<\/code>.\nThe root-to-leaf path 1->3<\/code> represents the number 13<\/code>.\nTherefore, sum = 12 + 13 = 25<\/code>.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> [4,9,0,5,1]\n    4\n   \/ \\\n  9   0\n \/ \\\n5   1\nOutput:<\/strong> 1026\nExplanation:<\/strong>\nThe root-to-leaf path 4->9->5<\/code> represents the number 495.\nThe root-to-leaf path 4->9->1<\/code> represents the number 491.\nThe root-to-leaf path 4->0<\/code> represents the number 40.\nTherefore, sum = 495 + 491 + 40 = 1026<\/code>.<\/pre>\n\n\n\n
Solution: Recursion<\/strong><\/h2>\n\n\n\n
Time complexity: O(n)
Space complexity: O(h)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int sumNumbers(TreeNode* root) {\n    int ans = 0;\n    function traverse = [&](TreeNode* t, int num) {\n      if (!t) return;\n      num = num * 10 + t->val;\n      if (t->left || t->right) {        \n        traverse(t->left, num);\n        traverse(t->right, num);\n      } else {        \n        ans += num;\n      }\n    };\n    traverse(root, 0);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the…<\/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,17,28],"class_list":["post-5738","post","type-post","status-publish","format-standard","hentry","category-tree","tag-medium","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5738","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=5738"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5738\/revisions"}],"predecessor-version":[{"id":5742,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5738\/revisions\/5742"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5738"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5738"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5738"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}