大连优化网站,网站建设费用的会计分录,做seo网站公司哪家好,家装网站建设预算提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣865. 具有所有最深节点的最小子树二、力扣1123. 最深叶节点的最近公共祖先三、力扣1026. 节点与其祖先之间的最大差值四、力扣1120. 子树的最大平均值 … 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣865. 具有所有最深节点的最小子树二、力扣1123. 最深叶节点的最近公共祖先三、力扣1026. 节点与其祖先之间的最大差值四、力扣1120. 子树的最大平均值 前言 二叉树的递归分为「遍历」和「分解问题」两种思维模式这道题需要用到「分解问题」的思维而且涉及处理子树需要用后序遍历
一、力扣865. 具有所有最深节点的最小子树
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode subtreeWithAllDeepest(TreeNode root) {Result res fun(root);return res.node;}public Result fun(TreeNode root){if(root null){return new Result(null,0);}Result left fun(root.left);Result right fun(root.right);if(left.depth right.depth){return new Result(root,left.depth1);}Result res left.depth right.depth ? left : right;res.depth res.depth 1;return res;}
}
class Result{public TreeNode node;public int depth;public Result(TreeNode node, int depth){this.node node;this.depth depth;}
}二、力扣1123. 最深叶节点的最近公共祖先
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public TreeNode lcaDeepestLeaves(TreeNode root) {Result res fun(root);return res.node;}public Result fun(TreeNode root){if(root null){return new Result(null,0);}Result left fun(root.left);Result right fun(root.right);if(left.depth right.depth){return new Result(root,left.depth1);}Result res left.depth right.depth ? left : right;res.depth res.depth 1;return res;}
}
class Result{public TreeNode node;public int depth;public Result(TreeNode node, int depth){this.node node;this.depth depth;}
}三、力扣1026. 节点与其祖先之间的最大差值
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {int res 0;public int maxAncestorDiff(TreeNode root) {fun(root);return res;}public int[] fun(TreeNode root){if(root null){return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};}int[] leftMinMax fun(root.left);int[] rightMinMax fun(root.right);int curMin Math.min(Math.min(leftMinMax[0],rightMinMax[0]),root.val);int curMax Math.max(Math.max(leftMinMax[1],rightMinMax[1]),root.val);res Math.max(res,Math.max(curMax - root.val, root.val - curMin));return new int[]{curMin,curMax};}
}四、力扣1120. 子树的最大平均值
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {double res 0;public double maximumAverageSubtree(TreeNode root) {fun(root);return res;}public double[] fun(TreeNode root){if(root null){return new double[]{0,0};}double[] left fun(root.left);double[] right fun(root.right);double curCount left[0] right[0] 1;double curSum left[1] right[1] root.val;res Math.max(res,curSum/curCount);if(curCount 1){return new double[]{curCount,root.val};}return new double[]{curCount,curSum};}
}
