给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入: [1,2,3] 1 / \ 2 3 输出: 6
解题思路:
我们从根节点开始递归,最大值的路径和可能出现在左子树,右子树以及包含根节点的左右子树三种情况。因此使用递归算法从根节点开始遍历,如果左右子树最大路径和大于0,则取出该路径的最大值,否则为零,也就是说如果大于零,则加上之后result是可以增加的!因此对result进行更新,同时递归函数也返回root->val + max(0, max(left, right))。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int result;
int dfs(TreeNode* root){
if(!root) return 0;
int left = max(dfs(root->left), 0);
int right = max(dfs(root->right), 0);
result = max(root->val+left+right, result);
return root->val + max(0, max(left, right));
}
int maxPathSum(TreeNode* root) {
if(!root) return 0;
result = root->val;
dfs(root);
return result;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
解题思路:
这是一个分治思路,求一个二叉树中存不存在某一个路径和为sum,可以变换问题为:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) return false;
if (root->left == NULL && root->right == NULL && root->val == sum) return true;
if (root->left != NULL && hasPathSum(root->left, sum - (root->val))) return true;
if (root->right != NULL && hasPathSum(root->right, sum - (root->val))) return true;
return false;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/path-sum
解题思路:
和上一题的思路一模一样,但这一题需要我们将中间遍历的节点值保存起来,因此需要一个tmp数组来保存我们遍历过的节点!这里面需要注意的一点就是回溯法的使用,当修改了一个状态之后,递归结束后,需要把这个状态重新置为之前的状态。 比如tmp中push_back了一个值,当递归结束进行回溯阶段,需要pop_back()。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> res; vector<int> tmp;
void dfs(TreeNode* root, int sum){
tmp.push_back(root->val); // 修改状态
if(root->left == NULL && root->right == NULL && sum == root->val){
res.push_back(tmp);
return;
}
if(root->left != NULL){
dfs(root->left, sum-root->val);
tmp.pop_back(); // 回溯
}
if(root->right != NULL){
dfs(root->right, sum-root->val);
tmp.pop_back(); // 回溯
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(root == NULL) return res;
dfs(root, sum);
return res;
}
};
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/path-sum-ii/