二叉树的最大深度
解法一
递归
class Solution { public int maxDepth(TreeNode root) { if(root == null)return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left,right)+1; } }
二叉树中的最大路径和
解法一
暴力递归
cur，left，right以及cur的父节点parent
第一种情况：以cur节点为根节点得到最大(cur+left+right)
第二种情况：以parent为根节点得到最大(parent+cur+Math.max(left,right))
这里只能取一边因为要构成路径
class Solution { int res = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { getMax(root); return res; } public int getMax(TreeNode root){ if(root == null) return 0; int cur = root.val; // 获取左边的值,如果为负数则不取左边 int left = Math.max(getMax(root.left),0); int right = Math.max(getMax(root.right),0); int sum = cur + left + right; res = Math.max(sum,res); // 取左右两边的大值返回给root的父节点使用 return cur + Math.max(left,right); } }
路径总和III
解法一
暴力
算出以节点为根节点满足条件的路径数
再算出每个节点的再相加
class Solution { //递归每一个节点 public int pathSum(TreeNode root, int targetSum) { int res = 0; if(root == null) return 0; res+=sum(root,targetSum); res+=pathSum(root.left,targetSum); res+=pathSum(root.right,targetSum); return res; } // 注意这里要用long public int sum(TreeNode root,long targetSum){ int res = 0; //递归结束条件 if(root == null) return 0; //当前节点满足了res++; if(targetSum == root.val){ res++; } //继续找左边 res+=sum(root.left,targetSum-root.val); //找右边 res+=sum(root.right,targetSum-root.val); return res; } }
解法二
前缀和
class Solution { public int pathSum(TreeNode root, int targetSum) { HashMap<Long,Integer> map = new HashMap<>(); map.put(0L,1); return sum(root,targetSum,0L,map); } // 注意这里要用long public int sum(TreeNode root,int targetSum,long curSum,HashMap<Long,Integer> map){ int res = 0; //递归结束条件 if(root == null) return 0; curSum = curSum+root.val; res+=map.getOrDefault(curSum-targetSum,0); map.put(curSum,map.getOrDefault(curSum,0)+1); //计算左右边 res+=sum(root.left,targetSum,curSum,map); res+=sum(root.right,targetSum,curSum,map); //移除当前 map.put(curSum,map.get(curSum)-1); return res; } }
