【钰娘娘】1373. 二叉搜索子树的最大键值和 DFS

【钰娘娘】1373. 二叉搜索子树的最大键值和 DFS

做题结果

成功，这题比较简单，其实只要搞懂两件事：是不是二叉搜索树，最大和是多少

方法：DFS

是不是二叉搜索树？

1. 左右子树都是二叉搜索树

2. 根节点的值需要大于左子树的最大值，小于右子树的最小值

3. 综上需要记录子树的 最大最小值以及是否二叉搜索树

最大和是多少？

1. 是二叉搜索树，才有必要把和计入答案

2. 需要知道子树和。当前树和 = 左子树和+右子树和+当前值

3. 综上需要记录子树和

所以每个节点返回时，需要提供四个信息：[最小值，最大值，和，是不是二叉搜索树]

class Solution { public int maxSumBST(TreeNode root) { getBSTMax(root); return res; } int res = 0; private int[] getBSTMax(TreeNode root){ if(root==null) return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE,0,1}; int[] ans = new int[4]; int[] left = getBSTMax(root.left); int[] right = getBSTMax(root.right); if(left[3]==1&&right[3]==1&&left[1]root.val){ ans = new int[]{Math.min(left[0],root.val),Math.max(right[1],root.val),root.val+left[2]+right[2],1}; res = Math.max(res,ans[2]); } return ans; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。