郴州网站推广公司排名,怎么查网站后台地址,开化网络营销怎么做,建设工程合同备案网站提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣1245. 树的直径二、力扣968. 监控二叉树三、力扣979. 在二叉树中分配硬币 前言 说过后序位置的特殊之处#xff0c;后序位置可以接收到子树的信息文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣1245. 树的直径二、力扣968. 监控二叉树三、力扣979. 在二叉树中分配硬币 前言 说过后序位置的特殊之处后序位置可以接收到子树的信息同时也可以通过函数参数接收到父节点传递的信息这道题就可以比较完美地体现这一特点
一、力扣1245. 树的直径
class Solution {int max 0;MapInteger,ListInteger map new HashMap();HashSetInteger set new HashSet();public int treeDiameter(int[][] edges) {if(edges.length 0){return 0;}for(int[] e : edges){int a e[0], b e[1];if(!map.containsKey(a)){map.put(a,new ArrayList());}if(!map.containsKey(b)){map.put(b, new ArrayList());}map.get(a).add(b);map.get(b).add(a);}fun(edges[0][0]);return max;}public int fun(int root){if(set.contains(root)){return 0;}set.add(root);int first 0, second 0;for(int a : map.get(root)){int child fun(a);if(child first){second first;first child;}else if(child second){second child;}}int cur first second;max Math.max(max, cur);return first 1;}
}二、力扣968. 监控二叉树
/*** 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 minCameraCover(TreeNode root) {if(fun(root) 0){res ;}return res;}//0表示未覆盖//1表示安装摄像头//2表示已覆盖public int fun(TreeNode root){if(root null){return 2;}int left fun(root.left);int right fun(root.right);if(left 0 || right 0){res ;return 1;}if(left 1 || right 1){return 2;}if(left 2 right 2){return 0;}return 0;}
}三、力扣979. 在二叉树中分配硬币
/*** 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 distributeCoins(TreeNode root) {fun(root);return res;}public int fun(TreeNode root){if(root null){return 0;}int left fun(root.left);int right fun(root.right);res Math.abs(left) Math.abs(right) root.val - 1;return left right root.val - 1;}
}
