赞
踩
模式识别:最大路径和 ——> 递归
递归公式
sum = 自己 + 左 + 右
递归中的返回结果
output = 自己 + max(左,右)
找结果——更新结果
maxSum = Math.max(maxSum, sum);
class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { // 递归 dfs(root); return maxSum; } public int dfs(TreeNode root){ // 1. 终止条件 if(root==null){ return 0; } // 2. 递归公式,递归逻辑 int left = dfs(root.left); int right = dfs(root.right); int sum = root.val + left + right; maxSum = Math.max(sum,maxSum); // 3. 每次返回值 int output = root.val + Math.max(left,right); if(output>0) return output; return 0; } }
public class treeMaxPath { static class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int x){ val = x; } } public static TreeNode build(Integer[] nums){ // 借助队列来构造树 Queue<TreeNode> queue = new LinkedList<>(); TreeNode root = new TreeNode(nums[0]); queue.offer(root); int index = 1; while(!queue.isEmpty()){ TreeNode node = queue.poll(); if(index<nums.length && nums[index]!=null){ node.left = new TreeNode(nums[index]); queue.offer(node.left); } index++; if(index<nums.length && nums[index]!=null){ node.right = new TreeNode(nums[index]); queue.offer(node.right); } index++; } return root; } public static int dfs(TreeNode root){ // 1.终止条件 if(root==null){ return 0; } // 2. 递归 int left = dfs(root.left); int right = dfs(root.right); int sum = root.val + left + right; maxSum = Math.max(sum,maxSum); int output = root.val + Math.max(left,right); if(output>0) return output; return 0; } static int maxSum = Integer.MIN_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("输入二叉树构造数组"); String input = sc.nextLine(); input = input.replace("[",""); input = input.replace("]",""); String[] parts = input.split(","); Integer[] nums = new Integer[parts.length]; for(int i = 0 ; i < parts.length;i++){ if(!parts[i].equals("null")){ nums[i] = Integer.parseInt(parts[i]); }else{ nums[i] = null; } } TreeNode root = build(nums); dfs(root); System.out.println("结果是"+maxSum); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。