530.二叉搜索树的最小绝对差
题目链接：力扣
思路
二叉搜索树是有序的。遇到在二叉搜索树上求什么最值，差值之类的，就把他想成在一个有序数组上求最值，求差值，这样就简单多了
二叉搜素树采用中序遍历就是一个有序数组
在一个有序数组上求两个数最小差值，就比较简单了
最直观的想法，就是把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了
二叉搜索树中的最小绝对差
借用数组
借用数组，将二叉树按照中序遍历一一添加到数组中，在数组中寻找最小差值
class Solution { List<Integer> listVal = new ArrayList<>(); public int getMinimumDifference(TreeNode root) { traversal(root); int result = Integer.MAX_VALUE; for (int i = 1; i < listVal.size(); i++) { int val = listVal.get(i) - listVal.get(i - 1); if (val < result) { result = val; } } return result; } public void traversal(TreeNode node) { if (node == null) { return; } // 左 traversal(node.left); // 中 listVal.add(node.val); // 右 traversal(node.right); } }
直接递归
两个指针指向，在cur离开最小值的之后给pre进行赋值，此后，两个指针紧紧相随
class Solution { // 定义结果变量 int result = Integer.MAX_VALUE; // 定义指针 TreeNode pre = null; public int getMinimumDifference(TreeNode root) { traversal(root); return result; } void traversal (TreeNode cur) { if (cur == null) { return; } // 左 traversal(cur.left); // 中 if (pre != null) { result = Math.min(result, cur.val - pre.val); } pre = cur; // 右 traversal(cur.right); } }
501.二叉搜索树中的众数
题目链接：力扣
思路
最直接的思路就是遍历整个二叉搜索树，同时用Map通知每个数字出现的次数，返回频率最高的数字的结果集，这样无疑是比较复杂的
再者，就是首先遍历一次二叉树，然后统计数字出现的最高频率。然后再遍历一次二叉树，找到出现频率最高的元素
这种遍历使用双指针遍历两次二叉树的做法还是比较复杂，如果在一次遍历中就将记录每个数字出现的频率、记录出现的最高频率数字，这两件事情同时一起做了呢？
那就是遍历相同节点的元素的时候给节点元素记录出现频率+1，并且如果记录的值等于目前统计的最大频率的时候就记录，就将元素添加进结果集。如果记录的新的count值大于目前统计的最大频率maxCount了，那就说明之前记录的数字都是不合适的，全部删除了，重新记录
二叉搜索树中的众数
class Solution { List<Integer> result; TreeNode pre; int count; int maxCount; public int[] findMode(TreeNode root) { pre = null; count = 0; maxCount = 0; result = new ArrayList<>(); traversal(root); int[] res = new int[result.size()]; for (int i = 0; i < result.size(); i++) { res[i] = result.get(i); } return res; } void traversal(TreeNode cur) { // 终止条件 if (cur == null) { return; } // 左 traversal(cur.left); // 中 if (pre == null || pre.val != cur.val) { // 这两种情况下count要从头开始记录，默认应该为1 count = 1; } else if (pre.val == cur.val) { // 当相等的时候，count进行记录 count++; } // 当count在不断记录的时候，也要时刻关注maxCount这边 if (count == maxCount) { result.add(cur.val); } else if (count > maxCount) { maxCount = count; result.clear(); result.add(cur.val); } // pre指针进行移动 pre = cur; // 右 traversal(cur.right); } }
236. 二叉树的最近公共祖先
题目链接：力扣
思路
已经触及目前我的理解上限了，就是很妙，就是很绝，思路就是很棒，很清楚，不得不感叹，今天跟着视频听了一遍，巧了两遍代码，稍微理解了
首先题目要求中确保p和q都在二叉树中
我们要寻找的是公共祖先，也就是我们要查找的这个祖先肯定是有自己的左节点和右节点的，所以是在中间节点上进行逻辑处理，所以采用的遍历方式是左右中
接下来就是分析q和p出现的所有情况：
1、p和q属于公共祖先的子树上的元素
1).一个在公共祖先的左子树上，一个在公共祖先的右子树上
2).两个都在公共祖先的左子树上
3).两个都在公共祖先的右子树上
2、p或q一个是公共祖先本身
其实情况1就将所有的情况2的情况就包含了
情况1的三种情况对节点返回结果处理的三种情况：
1、left != null && right != null
2、left != null && right == null
3、left == null && right != null
如果左右都不是空，那说明左右子树分别找到了一个节点，那该节点就是公共祖先了
如果左空右不空，那说明右边已经找到了公共祖先了，返回右节点带回来的就可以
如果右空左不空，那说明左边已经找到了公共祖先了，返回左节点带回来的就可以
二叉树的最近公共祖先
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } if (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; } return null; } }
