关于java:二叉树搜索子树的最大键值和

什么时候应用后序遍历呢？
如果以后节点要做的事件须要通过左右子树的计算结果推导进去，就要用到后序遍历
二叉树相干题目最外围的的思路就是明确以后节点须要做的事件是什么???
1.我必定得晓得左右子树是不是非法的BST,如果这俩儿子有一个不是BST，以我为根的这棵树必定不是BST。
2.如果左右子树都是非法的BST,我得瞅瞅左右子树加上本人还是不是非法的BST，因为依照BST的定义，以后节点的值应该大于左子树的最大值，小于右子树的最小值，否则就毁坏了BST的性质。
3.因为题目要计算最大的节点之和，如果左右子树加上我本人还是一棵非法的BST，也就是说以我为根的整棵树是一棵BST，那我须要晓得咱们这棵的所有节点之和是多少。
站在以后节点的视角，须要晓得以下具体信息:
1.左右子树是否是BST。
2.左子树的最大值和右子树的最小值。
3.左右子树的节点值之和。
尝试用伪码写出算法的大抵逻辑:

//全局变量，记录BST最大节点值和int maxSum=0;//遍历二叉树void traverse(TreeNode root){//base caseif(root==null){return;}//前序遍历代码//判断左右子树是不是BSTif(!isBST(root.left)||!isBST(root.right)){goto next;}//计算左子树的最大值和右子树的最小值int leftMax=findMax(root.left);int rightMin=findMin(root.right);//判断以root节点为根的树是不是BSTif(root.val<=leftMax||root.val>=rightMin){goto next;}//如果条件都合乎，计算以后BST的节点之和int leftSum=findSum(root.left);int rightSum=findSum(root.right);int rootSum=leftSum+rightSum+root.val;//计算BST节点的最大和this.maxSum=Math.max(maxSum,rootSum);//递归左右子树next:traverse(root.left);traverse(root.right);}//计算以root为根的二叉树的最大值int findMax(TreeNode root){}//计算以root为根的二叉树的最小值int findMin(TreeNode root){};//计算以root为根的二叉树的节点和int findSum(TreeNode root){};//判断以root为根的二叉树是否是BSTboolean isBST(TreeNode root){}

其中四个辅助函数比较简单，其中只有判断非法BST的函数稍有技术含量，前文二叉搜寻树操作集锦
稍作剖析就会发现，这几个辅助函数都是递归函数，都要遍历输出的二叉树，外加traverse函数自身的递归，能够说是递归上加递归，所以复杂度很高
只有把前序遍历变成后序遍历,让traverse函数把辅助函数做的事顺便做掉

int maxSum=0;int [] traverse(TreeNode root){int[] left=traverse(root.left);int[] right=traverse(root.right);}

traverse(root)返回一个大小为4的int数组，咱们暂且称他为res,其中:
res[0]-记录以root为根的二叉树是否是BST，若为１则阐明是BST，若为０则阐明不是BST。
res[1]-记录以root为根的二叉树的所有节点中的最小值
res[2]-记录以root为根二叉树所有节点中的最大值
res[3]-记录以root为根的二叉树所有节点值之和
咱们要视图通过left和right正确地导出res数组

int[] traverse(TreeNode root){if(root==null){return new int[]{1,Integer>MAX_VALUE,Integer>MIN_VALUE,0};}//递归计算左右子树int [] left=traverse(root.left);int [] right=traverse(root.right);int[] res=new int[4];//这个if在判断以root为根的二叉树是不是BSTif(left[0]==1&&right[0]==1&&root.val>left[2]&&root.val<right[1]){//以root为根的是二叉树是BSTres[0]=1;res[1]=Math.min(left[1],root.val);res[2]=Math.max(right[2],root.val);res[3]=left[3]+right[3]+root.val;maxSum=Math.max(maxSum,res[3]);}else{res[0]=0;}return res;}

这后序遍历也不是乱用的，这里为什么能用呢？？？
以root为根的二叉树的节点之和，是不是能够通过左右子树的和加上root.val计算出来？
以root为根的二叉树的最小值/最大值，是不是能够通过左右子树的最小值/最大值和root.val比拟进去？
判断以root为根的二叉树是不是BST，是不是得先判断左右子树是不是BST?是不是还得看看左右子树左右子树的最大值和最小值？
如果以后节点要做的事件须要通过通过左右子树的计算结果推导进去，就要用到后序