二叉树路径和

二叉树中和为某一值的路径

  vector<vector<int>> res;
  
  vector<vector<int>> pathTarget(TreeNode *root, int target) {
    dfs(root, target, 0);
    return res;
  }
  
  vector<int> paths;
  // 优化2: 外层记录 path，dfs 只传 sum
  void dfs(TreeNode *root, int target, int sum) {
    if (root == nullptr) return;

    sum += root->val;
    paths.push_back(root->val);
    if (target == sum && !root->left && !root->right) {
      res.push_back(paths);
    }
    // 中左右，前序遍历
    if (root->left) dfs2(root->left, target, sum);
    if (root->right) dfs2(root->right, target, sum);

    paths.pop_back();
  }

二叉树的最大路径和

int max_sum = INT_MIN;
int maxPathSum(TreeNode *root) {
  dfs(root);
  return max_sum;
}
// 计算以当前节点，向下延伸的路径的最大贡献度，只可能有三种情况(节点自己，节点+左子节点，节点+右子节点)
int dfs(TreeNode *root) {
  if (root == nullptr) return 0;

  // 最大贡献度
  int left = max(dfs(root->left), 0);
  int right = max(dfs(root->right), 0);

  // 计算最大路径和
  int all = root->val + left + right;
  max_sum = max(max_sum, all);

  return root->val + max(left, right);
}