题目链接:https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int dfs(TreeNode* root, int val) { int sum = 0; if (!root) { return sum; } else { sum = root->val; } sum = (val<<1) | sum; // 这里是关键点2,要把上一层的和左移,或上当前节点的值。我是想到了左移,和加上当前节点的值 if (!root->left && !root->right) { return sum; } // 这里是关键点3,深度优先遍历,左 - 右 - 根 int left = 0; int right = 0; if (root->left) { left = dfs(root->left, sum); } if (root->right) { right = dfs(root->right, sum); } sum = left + right; return sum; } int sumRootToLeaf(TreeNode* root) { return dfs(root, 0); // 这里是关键点1,要抽出来一个新的函数用来递归,并且要把二叉树上一层的和传递到下一层,用来累计。我没想到抽出来新的函数并且把上一层的累计和传进去 } }; |