to traverse the tree, keeping track of the current path value val (as a binary number). At each node, compute val = (val << 1) | node.val. When we reach a leaf, add val to the running result res. Implement this recursively starting from root with initial val = 0.

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(h) where h is the height of the tree

Code

[{"language":"C++","code":"struct TreeNode {\n    int val;\n    TreeNode *left;\n    TreeNode *right;\n    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n};\nclass Solution {\npublic:\n    int sumRootToLeaf(TreeNode* root, int val = 0) {\n        if (!root) return 0;\n        val = (val << 1) | root->val;\n        if (!root->left && !root->right) return val;\n        return sumRootToLeaf(root->left, val) + sumRootToLeaf(root->right, val);\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">struct</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> TreeNode</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> val;</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    TreeNode </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">*</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">left;</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    TreeNode </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">*</span>&#x

Related Tags