112 path sum
Given a binary tree root and a value sum, judge whether there is a path where the sum of node values from the root node to the leaf node is equal to sum.
Enter a binary tree and a given integer, and output a Boolean value to indicate whether there are paths that meet the conditions.
Input: root = [5,4,8,11, null, 13,4,7,2, null, null, 1], targetsum = 22
Output: true
Explanation: the path from root node to leaf node equal to the target sum is [5,4,11,2].
Resolution:
Note that leaf nodes refer to nodes without child nodes. The path can only be from parent node to child node, not from child node to parent node.
For a binary tree, the path from any given node to the root node is uniquely fixed. Therefore, the sum of its corresponding paths is also unique and fixed.
Therefore, the binary tree can be traversed by using the preorder method, and the val value in each node can be replaced by the sum of the vals of its corresponding path. During traversal, check whether val of leaf node is equal to sum.
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(!root){
return false;
}
// Determine whether it is a leaf node
if(!root->left && !root->right && root->val==sum){
return true;
}
return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right,sum-root->val);
}
};
113 path sum II
Given the root node root and an integer expectNumber of a binary tree, find all paths where the sum of node values in the binary tree is the target value.
Input a binary tree and an integer, and output a two-dimensional matrix to represent all paths with the sum of expectNumber.
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2], [5,8,4,5]]
Resolution:
Depth first search can be used to enumerate each path from root node to leaf node.
When we traverse the leaf node and the path sum is just the target sum, we find a path that meets the conditions and add the path to the result set.
class Solution {
public:
void helper(TreeNode* root, int sum, vector<int>& path, vector<vector<int>>& paths){
path.push_back(root->val);
if(sum == root->val && !root->left && !root->right){
paths.push_back(path);
}
if(root->left){
helper(root->left,sum - root->val,path,paths);
}
if(root->right){
helper(root->right, sum - root->val,path,paths);
}
path.pop_back();
}
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> paths;
vector<int> path;
if(!root){
return paths;
}
helper(root,expectNumber,path,paths);
return paths;
}
};
437 path sum III
Given an integer binary tree, find how many paths the sum of node values is equal to the given value.
Enter a binary tree and a given integer, and output an integer indicating how many paths meet the conditions.
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Resolution:
The key to this problem is to calculate the path and. Therefore, when recursing each node, we need to consider the following situations:
- If you select this node to join the path, you must continue to join continuous nodes or stop joining nodes
- If the node is not selected to join the path, the left and right nodes will be reconsidered
Therefore, a convenient method is to create a sub function to calculate the path of continuous joining nodes. The auxiliary function recursively subtracts the path node value with the given value, and the final given value is reduced to 0 to form a path.
class Solution {
public:
int pathWithRoot(TreeNode* root, int sum){
if(!root){
return 0;
}
int count = 0;
// If the current node value is consistent with the path and, a path is formed
if(root->val == sum){
count = 1;
}else{
count = 0;
}
// Continue to find the path to the left and right child nodes
count += pathWithRoot(root->left, sum-root->val);
count += pathWithRoot(root->right, sum-root->val);
return count;
}
int pathSum(TreeNode* root, int targetSum) {
if(!root){
return 0;
}
// Add the current node to the path
int ans = 0;
ans = pathWithRoot(root,targetSum);
// Instead of adding the current node to the path, start looking for a new path from the left and right child nodes
ans += pathSum(root->left,targetSum);
ans += pathSum(root->right,targetSum);
return ans;
}
};
404 sum of left leaves
Given a binary tree, calculate the sum of all left leaves of the tree
Input a binary tree and output an integer to represent the sum of all left leaves
Input:
3 / \ 9 20 / \ 15 7
Output: 24
Explanation: in this binary tree, there are two left leaves, 9 and 15 respectively, so 24 is returned
Resolution:
The key to this problem is to use the definition of the left leaf node to conditionally recursively traverse the binary tree. At the same time, it is necessary to judge whether a node is a leaf node and define an auxiliary function. If the node has no child nodes, it means that the node is a leaf node.
If a node is a left leaf node, it is the left child node of a node, and it is also a leaf node.
According to this definition, in the recursive traversal process, if a node has a left child node and the node is a leaf node, the left child node is added to the cumulative sum; If the left child node is not a leaf node, the left child node is used as the root node to recursively find the left leaf node.
If a node has a right child node and the node is a leaf node, it will not accumulate and terminate the downward recursion; If the right child node is not a leaf node, the right child node is used as the root node to recursively find the left leaf node.
class Solution {
public:
bool isLeafNode(TreeNode* root){
return !root->left && !root->right;
}
int sumOfLeftLeaves(TreeNode* root) {
if(!root){
return 0;
}
int ans = 0;
if(root->left){
ans += isLeafNode(root->left)?root->left->val:sumOfLeftLeaves(root->left);
}
if(root->right){
ans += isLeafNode(root->right)?0:sumOfLeftLeaves(root->right);
}
return ans;
}
};
reference material
LeetCode 101: easy to brush with you (C + +) Chapter 14 pointer to the tree of three swordsmen