力扣labuladong——一刷day58

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

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

文章目录

前言
一、力扣333. 最大 BST 子树
二、力扣366. 寻找二叉树的叶子节点
三、力扣508. 出现次数最多的子树元素和
四、力扣563. 二叉树的坡度

前言

二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要混用两种思维。

一、力扣333. 最大 BST 子树

/*** 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 count = 0;int res = 0;TreeNode pre = null;boolean flag = true;public int largestBSTSubtree(TreeNode root) {if(root == null){return 0;}fun(root);if(flag){res = Math.max(res,count);System.out.println(res);}flag = true;count = 0;pre = null;largestBSTSubtree(root.left);largestBSTSubtree(root.right);return res;}public void fun(TreeNode root){if(root == null){return ;}count ++;fun(root.left);if(pre != null){if(root.val <= pre.val){flag = false;}}pre = root;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 {int res = 0;public int largestBSTSubtree(TreeNode root) {fun(root);return res;}//第一个为左子树最大值，第二个为右子树最小值，第三个为节点数public int[] fun(TreeNode root){if(root == null){return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE,0};}int[] leftArr = fun(root.left);int[] rightArr = fun(root.right);if(leftArr == null || rightArr == null){return null;}int leftMin = leftArr[0], leftMax = leftArr[1], leftCount = leftArr[2];int rightMin = rightArr[0], rightMax = rightArr[1], rightCount = rightArr[2];if(root.val > leftMax && root.val < rightMin){int curMin = Math.min(leftMin,root.val);int curMax = Math.max(rightMax,root.val);int curCount = leftCount + rightCount +1;res = Math.max(res,curCount);return new int[]{curMin, curMax, curCount};}return null;}
}

二、力扣366. 寻找二叉树的叶子节点

/*** 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 {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> findLeaves(TreeNode root) {fun(root);return res;}public int fun(TreeNode root){if(root == null){return 0;}int h = Math.max(fun(root.left),fun(root.right)) + 1;if(res.size() < h){res.add(new ArrayList<>());}res.get(h-1).add(root.val);return h;}
}

三、力扣508. 出现次数最多的子树元素和

/*** 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 flag = 0;Map<Integer,Integer> map = new HashMap<>();public int[] findFrequentTreeSum(TreeNode root) {List<Integer> list = new ArrayList<>();fun(root);Set<Map.Entry<Integer,Integer>> entrySet = map.entrySet();entrySet.stream().forEach(entry -> {int key = entry.getKey();int value = entry.getValue();if(value == flag){list.add(key);}});return list.stream().mapToInt(i -> i).toArray();}public int fun(TreeNode root){if(root == null){return 0;}int leftSum = fun(root.left);int rightSum = fun(root.right);int curSum = leftSum + rightSum + root.val;map.put(curSum,map.getOrDefault(curSum,0)+1);flag = Math.max(flag,map.get(curSum));return curSum;}
}

四、力扣563. 二叉树的坡度

/*** 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 findTilt(TreeNode root) {fun(root);return res;}public int fun(TreeNode root){if(root == null){return 0;}int leftSum = fun(root.left);int rightSum = fun(root.right);int curK = Math.abs(leftSum - rightSum);res += curK;return (leftSum + rightSum + root.val);}
}