leetcode刷题day18|二叉树Part06（ 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先）
530.二叉搜索树的最小绝对差
二叉搜索树的中序遍历是有序的。
思路：建立一个指针存放前一个节点；一个全局变量result存储结果。计算当前节点与前一个节点的差值，记录最小的差值。
中序遍历递归三步曲：
1、传入参数：根节点，无返回值
2、终止条件：当节点为空时，return。
3、递归逻辑：递归调用左子树；如果前一个节点不为空，计算差值并比较差值与result；将当前节点赋值给前一个节点；递归调用右子树。
代码如下：
class Solution {int result;TreeNode pre;public int getMinimumDifference(TreeNode root) {result=Integer.MAX_VALUE;getMinDiff(root);return result;}public void getMinDiff(TreeNode root){if(root==null) return;getMinDiff(root.left);if(pre!=null){result=Math.min(result,root.val-pre.val);}pre=root;getMinDiff(root.right);}
}
501.二叉搜索树中的众数
首先想到的把二叉树全部遍历一遍，将元素和出现的次数使用HashMap存放，排序后输出出现次数靠前的元素。但这样没有用到二叉搜索树的特殊属性且需要额外的空间。
所以考虑中序遍历递归，遍历得到的元素是从小到大按顺序排列的，记录元素出现的次数，并使用一个最大次数记录出现的最多的次数。如果元素出现的次数等于最大次数，则将当前元素加入集合中；如果大于最大次数，则清空集合中的元素，将当前元素加入。
递归三部曲：
1、传入参数：root；定义全局变量元素列表，所以不需要返回值；
2、终止条件：节点为空，return
3、递归函数逻辑：递归调用左节点，中间节点逻辑：如果前一个节点p re为空或者当前节点不等于前一个节点，count=1重新计数；否则count++；如果元素出现的次数等于最大次数，则将当前元素加入集合中；如果大于最大次数，更新最大次数，则清空集合中的元素，将当前元素加入。递归调用右节点。
代码
class Solution {List<Integer> list;TreeNode pre;int count;int maxCount;public int[] findMode(TreeNode root) {list=new ArrayList<>();count=0;maxCount=0;findMode1(root);int[] res=new int[list.size()];for(int i=0;i<list.size();i++){res[i]=list.get(i);}return res;}public void findMode1(TreeNode root){if(root==null) return;findMode1(root.left);if(pre==null || root.val!=pre.val){count=1;}else count++;if(count>maxCount){maxCount=count;list.clear();list.add(root.val);}else if(count==maxCount){list.add(root.val);}pre=root;findMode1(root.right);}
}
注意：要写清判断逻辑，不然会重复加元素。
236. 二叉树的最近公共祖先
要找最近公共祖先，最好的方法就是从下往上遍历，后序遍历就很适合。
存在两种情况，一种情况是p,q分别在左右两棵子树上，此时遇到p返回p，遇到q返回q，当左右子树都有返回值时该中间节点即为最近的公共祖先。第二种情况是p或q本身就是公共祖先，返回当前节点即可。第一种情况的逻辑已经包含了第二种情况。
递归三步曲：
1、输入参数：root，p,q，返回值为节点类型
2、终止条件：节点为null,p,q，直接返回节点。
3、递归函数逻辑：递归调用左子树，递归调用右子树，如果left 和 right都不为空，说明此时root就是最近公共节点；如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然。
代码：
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null || root==p || root==q) return root;TreeNode left=lowestCommonAncestor(root.left,p,q);TreeNode right=lowestCommonAncestor(root.right,p,q);if(left!=null && right!=null){return root;}else if(left!=null && right==null){return left;}else if(left==null && right!=null){return right;}else{return null;}}
}