什么时候应用后序遍历呢？
如果以后节点要做的事件须要通过左右子树的计算结果推导进去，就要用到后序遍历
二叉树相干题目最外围的的思路就是明确以后节点须要做的事件是什么???
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 case
if(root==null){return;}
// 前序遍历代码
// 判断左右子树是不是 BST
if(!isBST(root.left)||!isBST(root.right)){goto next;}
// 计算左子树的最大值和右子树的最小值
int leftMax=findMax(root.left);
int rightMin=findMin(root.right);
// 判断以 root 节点为根的树是不是 BST
if(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 为根的二叉树是否是 BST
boolean 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，若为1则阐明是 BST，若为0则阐明不是 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 为根的二叉树是不是 BST
if(left[0]==1&&right[0]==1&&root.val>left[2]&&root.val<right[1]){
// 以 root 为根的是二叉树是 BST
res[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? 是不是还得看看左右子树左右子树的最大值和最小值？
如果以后节点要做的事件须要通过通过左右子树的计算结果推导进去，就要用到后序