437. 路径总和 III

双重递归
image.png
image.png
count(TreeNode node,int targetSum) 计算以node为起点，目标和为targetSum的路径。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     int sum;
  18.     public int pathSum(TreeNode root, int targetSum) {
  19.       if(root==null) return 0;
  20.       count(root,targetSum);
  21.       pathSum(root.left, targetSum);
  22.       pathSum(root.right, targetSum);
  23.       return sum;
  24.     }
  26.     private void count(TreeNode node,int targetSum){
  27.       if(node==null) return;
  28.       if(node.val==targetSum) sum++;
  29.       count(node.left, targetSum-node.val);
  30.       count(node.right,targetSum-node.val);
  31.     }
  32. }


124. 二叉树中的最大路径和

  1. class Solution {
  2.     int ans=Integer.MIN_VALUE;
  3.     public int maxPathSum(TreeNode root) {
  4.         if(root==null) return 0;
  5.         getMax(root);
  6.         return ans;
  7.     }
  9.     public int getMax(TreeNode root){
  10.         if(root==null) return 0;
  11.         int left=Math.max(0,getMax(root.left));
  12.         int right=Math.max(0,getMax(root.right));
  13.         ans=Math.max(ans,left+right+root.val);
  14.         return Math.max(left,right)+root.val;
  15.     }
  16. }