力扣labuladong——一刷day60

本文主要是介绍力扣labuladong——一刷day60，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、力扣663. 均匀树划分
二、力扣687. 最长同值路径
三、力扣814. 二叉树剪枝

前言

二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「分解问题」的思维，而且涉及处理子树，需要用后序遍历。

一、力扣663. 均匀树划分

/*** 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 {HashSet<Integer> set = new HashSet<>();public boolean checkEqualTree(TreeNode root) {int count = root.val + fun(root.left) + fun(root.right);if(count % 2 != 0){return false;}return set.contains(count/2);}public int  fun(TreeNode root){if(root == null){return  0;}int left = fun(root.left);int right = fun(root.right);int cur = left + right + root.val;set.add(cur);return cur;}
}

二、力扣687. 最长同值路径

/*** 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 longestUnivaluePath(TreeNode root) {if(root == null){return 0;}fun(root);return res-1;}public int fun(TreeNode root){if(root == null){return 0;}int left = fun(root.left);int right = fun(root.right);int cur = 1, curLeft = 1, curRight = 1;if(root.left != null){if(root.left.val == root.val){cur += left;curLeft += left;}}if(root.right != null){if(root.right.val == root.val){cur += right;curRight += right;}}res = Math.max(res,cur);return Math.max(curLeft,curRight);}
}

三、力扣814. 二叉树剪枝

/*** 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 {boolean flag = true;public TreeNode pruneTree(TreeNode root) {if(root == null){return null;}fun(root);if(flag){return null;}flag = true;root.left = pruneTree(root.left);root.right = pruneTree(root.right);return root;}public void fun(TreeNode root){if(root == null){return ;}if(root.val == 1){flag = false;}fun(root.left);fun(root.right);}
}

减枝

/*** 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 pruneTree(TreeNode root) {if(root == null){return null;}root.left = pruneTree(root.left);root.right = pruneTree(root.right);if(root.left == null && root.right == null && root.val == 0){return null;}return root;}
}