/**
* 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) {}
* };
*/
// 复习
// 此题整体思路不难,会想到dfs+回溯的思想解决,难的地方在于实现,毕竟不是典型的回溯问题,怎么在递归中写出正确的回溯逻辑是难点。
// 此题证明了,根据我自己总结的,dfs有2种写法,即“先污染后治理”或“干脆直接就不污染”这2种思想都是行得通的,关键在于哪种场景使用会更好。
// 此题还有值得注意的一点,就是当遇到的不是典型回溯问题时,怎么在dfs中构建出回溯的思想?
// 比如:回溯模板中,是有for()循环的,然后for(){com.push();dfs();com.pop()}的写法,但此题没for(),如何在dfs(l);dfs(r)这里构建出回溯。
// 此外,二叉树的前、中、后序遍历,与dfs的思想的异同点(其实就是一样的)。
// string("123")->char(1)char(2)char(3),atoi(str.c_str())将"123"->123,这是有趣且实用的工具。
class Solution {
public:
void dfs(TreeNode* node, vector<string>& coms, string& com) {
// 这是dfs的“先污染后治理”写法,会在最底层的node进来后,再判空退出。
// 这种是比较通常的写法,但在此题是不好使的,因为需要同时判断一个node的下方left、right是否都还有连接,如果没有,就不用继续;如果有,就要继续。
// 这决定了什么时候让coms这个“装阶段性结果的篮子”能够push_back,如果采用“先污染后治理”,那么可能会装2次同样的结果,还可能有其他问题。
// 比如:
// 4
// 9 0
// 5 1
// 当遍历到5时,由于5的下方l、r都为空,则会污染两次,如果都给coms装篮,就会有上述重复问题,会把495这个数装两次。
// 再比如
// 4
// 9 0
// 1
// 当遍历到9时,由于9的l为空,此时会先污染9的下方左l,然后直接装篮???这是错误的行为,因为49不是阶段性结果,491才是。
// if (node == nullptr) {
// coms.push_back(com);
// return;
// }
// com.push_back(node->val + '0');
// dfs(node->left);
// dfs(node->right);
// com.pop_back();
// 所以正确的做法是,采用dfs中“干脆直接就不污染”的方法。这种写法的特点是,终止条件只有1个,就是dfs结束的return,而没有入口的return,因为直接被拦在了上一层。
// 模板是:提前判断node->left、node->right的边界有效性。当进入条件后,第一时间将com装篮(当前node的下一层node,非当前node)。
// 因此,需要提前将root装篮,在外面就进行。因为进来后,边界条件通过后,就装的是下一层node了。
if (node->left) {
com.push_back(node->left->val + '0');
dfs(node->left, coms, com);
}
if (node->right) {
com.push_back(node->right->val + '0');
dfs(node->right, coms, com);
}
// 这里就是不用“先污染后治理的原因”,我在上一层node的上帝视角,提前做好判断。只有下一层l、r都没时,才会coms阶段性装篮,否则就不会。
// 比如
// 4
// 9 0
// 1
// 当走到9时,就直接com装1;当走到1时,下一层l、r都没了,才coms装491。
if (node->left == nullptr && node->right == nullptr) {
coms.push_back(com);
}
// 最后在这里体现“回溯”,这点其实比较难想,但前面的基础有了后,这里可以尝试推出来。
com.pop_back();
}
int sumNumbers(TreeNode* root) {
vector<string> coms;
string com = "";
// “干脆直接就不污染”,提前push root。
com.push_back(root->val + '0');
dfs(root, coms, com);
// string("123")->char(1)char(2)char(3),atoi(str.c_str())将"123"->123,这是有趣且实用的工具。
int sum = 0;
for (auto str:coms) {
sum += atoi(str.c_str());
}
return sum;
}
};