二叉树的第六天！
题目链接：530. 二叉搜索树的最小绝对差
状态：可以用比较麻烦的方法做出来。
利用二叉搜索树的性质可以很轻易的利用中序遍历得到有序排列的元素，随后比较相邻的元素值，记录最小值即可。但是实际上，使用双指针的方法可以避免开辟额外的空间来记录这些元素，是一种优化方案。
事实上，这种优化方案并不难，就是在每次记录的基础上额外添加一个指针记录上一个节点，这样就可以方便他俩比较值了。完整代码如下：
class Solution { // Java
TreeNode pre; // 记录上一个遍历的节点
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root == null) return 0;
traversal(root);
return result;
}
public void traversal(TreeNode root){
if(root == null) return;
//left
traversal(root.left);
// mid
if(pre != null){
result = Math.min(result, root.val - pre.val);
}
pre = root;
// right
traversal(root.right);
}
}
复杂度分析：
时间复杂度：O(n). 每个节点遍历一次
空间复杂度：O(h). 递归深度取决于树的高度h
题目链接：501. 二叉搜索树中的众数
状态：可以用比较麻烦的方法做出来。
暴力法可以先遍历一边，然后用map记录每个数字出现的次数，最后找出最高次数，然后在第二遍遍历的时候把最高次数的元素找出来。这种方式需要遍历两次二叉树。
利用二叉搜索树的性质可以知道同一种数字出现的位置一定是相邻的。因此就可以通过判断相邻的数字是否相同来计数，如果相同则count+1；如果不相同则说明接下来的是新数字，那么就把count设置为1，表示重新开始计数新一个数字。在此基础上，我们设置一个实时更新的代码，目的是为了只用遍历一次二叉树就获取结果。具体做法为：当coung = maxCount的时候我们就把结果加入到结果集中，但是如果count > maxCount时，就表示之前所有的记录结果都没用了，所以我们先清除掉之前的结果然后再重新加入当前的结果，同时记得更新maxCount。完整代码如下：
class Solution { // Java
ArrayList<Integer> resList;
int maxCount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root) {
resList = new ArrayList<>();
maxCount = 0;
count = 0;
pre = null;
findMode1(root);
int[] res = new int[resList.size()];
for(int i = 0; i < resList.size(); i++){
res[i] = resList.get(i);
}
return res;
}
public void findMode1(TreeNode root){
if(root == null) return;
findMode1(root.left);
int rootValue = root.val;
// 计数
if(pre == null || rootValue != pre.val){
count = 1 ;
}else{
count ++;
}
// update result and maxCount
if(count > maxCount){
resList.clear();
resList.add(rootValue);
maxCount = count;
}else if(count == maxCount){
resList.add(rootValue);
}
pre = root;
findMode1(root.right);
}
}
复杂度分析：
时间复杂度：O(n). 每个节点遍历一次
空间复杂度：O(h) + O(n) = O(n). 递归部分取决于树高h，另一部分是存放结果的数组大小，这个取决于结果有多大，最坏的结果是所有结果都要存，所以是O(n)， 二者相加 最坏还是O(n)级别。
题目链接：236. 二叉树的最近公共祖先
状态：想到了是后序遍历，但没做出来。
本题的思路是遍历到了p或q就向上返回，然后分几种情况来返回结果：对于一个节点，1. 如果左边返回上来有结果，右边是null，则向上返回左边结果；2. 如果左边为null，右边返回上来有结果，则向上返回右边结果；3. 如果两边都没结果那就返回空； 4.如果两边都有结果那就返回当前节点。这样就分别对应了四种情况：结果来源于左子树、结果来源于右子树、当前节点下还没找到结果、当前节点就是结果。
然后在一层一层往上返回时同样也遵循这个结果。举例说明，假设已经在二叉树中间段找到一个节点为结果节点，那在向上传递的过程中，对于他的父节点来说，只有他这一边是有结果的，另一边为null，所以他的父节点往上传的时候就会把他这个节点作为结果往上传。
完整代码如下：
class Solution { // Java
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q){ // Recursion termination condition
return root;
}
// Post-order traversal
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null){
return null;
}else if(left == null && right != null){ // find one side
return right;
}else if(left != null && right == null){ // find one side
return left;
}else{ // find both sides
return root;
}
}
}
复杂度分析：
时间复杂度：O(n). 每个节点遍历一次
空间复杂度：O(h). 递归深度取决于树的高度h
