【leetcode题解C++】257.二叉树的所有路径 and 404.左叶子之和 and 112.路径总和

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

思路：递归，结束条件是一个结点没有左孩子和右孩子。题目提示中写到至少会有一个根节点，那么不用判断树空的情况。

代码实现：

class Solution {void generate(TreeNode *node, string path, vector<string> &result) {path += to_string(node->val);if(node->left && !node->left->left && !node->left->right) {result.push_back(path);return;}if(node->left) generate(node->left, path + "->", result);if(node->right) generate(node->right, path + "->", result);}    vector<string> binaryTreePaths(TreeNode* root) {string path = "";vector<string> result;//if(!root) return result;generate(root, path, result);return result;}
};

404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

思路：递归，迭代都可以。迭代的话，前中后续都可行，下面的代码是后序遍历，注意判断左叶子结点即可。递归的判定条件也是相同的。

代码实现1：迭代

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack<TreeNode *> stk;if(!root) return 0;stk.push(root);int ret = 0;TreeNode *node;while(!stk.empty()) {node = stk.top();stk.pop();if(node->left && !node->left->left && !node->left->right) ret += node->left->val;if(node->left) stk.push(node->left);if(node->right) stk.push(node->right);}return ret;}
};

代码实现2：递归

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(!root) return 0;int leftValue = 0;if(root->left && !root->left->left && !root->left->right) {leftValue = root->left->val;}return leftValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);}
};

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

思路：递归+回溯，当得到的结果不满足时，需要往回退一步，寻找新的可能满足需求的路径。

代码实现：

class Solution {
public:bool calculate(TreeNode *node, int count) {if(!node->left && !node->right && count == 0) return true;if(!node->left && !node->right) return false;if(node->left) {count -= node->left->val;if(calculate(node->left, count)) return true;count += node->left->val;}if(node->right) {count -= node->right->val;if(calculate(node->right, count)) return true;count += node->right->val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(!root) return false;return calculate(root, targetSum - root->val);}
};