1. LeetCode 530. 二叉搜索树的最小绝对差
1.1 思路
- 因为是二叉搜索树，按照中序遍历是一个有序序列，此时相邻的两个节点的值就是最小绝对差
- 我们用双指针，一个指向前面pre一个紧跟后面root，用result记录root.val-pre.val的差的最小值。result和pre记录为全局变量
- 递归函数的参数和返回值：返回值为void，参数就是节点
- 终止条件：遇到空了就返回return
- 单层递归的逻辑：因为我们用中序遍历，左中右。就先向左遍历：travelsal(root.left)。然后是中，比较两节点的差值和result，让result记录最小值，因为最开始pre初始化为空，因此要判断pre是否为空，不为空就执行result=Math.min(result, root.val-pre.val)，就是当前节点-上一个节点的差。然后pre=root，这里为什么pre是指向前一个节点呢？因为最开始pre是null，不执行比较数值的逻辑，那么pre更新为root，然后进入递归函数，root更新，此时就是一前一后了。然后是向右遍历：travelsal(root.right)
1.2 代码
// class Solution { 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; //左 traversal(root.left); //中 if(pre!=null){ result = Math.min(result,root.val-pre.val); } pre = root; //右 traversal(root.right); } }
2. LeetCode 501. 二叉搜索树中的众数
2.1 思路
- 因为是二叉搜索树，按照中序遍历是一个有序序列，就用中序遍历
- 我们要先记录下最高频率maxCount，然后再遍历一遍二叉树，这样是遍历两次二叉树，其实可以不用这样。
- 我们依旧是用双指针的方式，root和pre，如果cur和pre相等的情况就count++，默认count=1，当cur和pre不相等了就count重新归一，那如果收获结果集呢？如果count和maxCount相等就加入到结果集result，那如果之前没遍历过二叉树怎么知道maxCount呢？这里设计一个代码技巧。
- 定义全局变量前一个节点pre，当前频率count，最高频率maxCount，结果集result。
- 递归函数的返回值和参数：返回值void，因为结果是放入到全局变量result，参数就是当前节点root
- 终止条件：如果root==null就返回return
- 单层递归逻辑：中序遍历，“左中右”，先向左遍历，函数(root.left)
- “中”的逻辑就是如果pre==null，那么count=1，此时pre还没指向节点，root是第一个节点。当pre不再指向空时，那当root.val==pre.val时就count++，否则就是pre和root的值不相等，count就重新归一，pre=root，让pre跟在root后面。统计出来后如果count==maxCount就把当前数值放入result结果集中。这里可能疑惑maxCount还没赋值吧？后面说。如果count>maxCount，就更新maxCount的值为count，那由于上面的逻辑是count==maxCount就把元素放入结果集里了，那说明之前放入结果集里的都不是我们想要的最高频率的结果，那就把result结果集清空，再把当前root.val的结果放入result中，此时这个才是我们最高频率的元素
- 右的逻辑就是，函数(root.right)。以上就是中序遍历的顺序
2.2 代码
// class Solution { 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++; } // 更新结果以及maxCount if (count > maxCount) { resList.clear(); resList.add(rootValue); maxCount = count; } else if (count == maxCount) { resList.add(rootValue); } pre = root; findMode1(root.right); } }
3. LeetCode 236. 二叉树的最近公共祖先
3.1 思路
- 找到p和q以后，然后往上去遍历，汇聚到一个节点，那这个节点就是最近公共祖先，其实二叉树没办法从下往上去遍历，但可以从下往上处理。按照二叉树递归的逻辑，有递归就有回溯，回溯就是从下往上处理的过程，这样可以判断某个节点左子树有没有出现过p或者q，右子树有没有出现过q或者p，想在回溯达到这个效果就要用后序，左右中
- 向左遍历就是找有没有出现过p或者q，向右遍历就是找有没有出现过p或者q，然后中就判断左右是否不为空，如果都不为空就证明这个“中”就是最近公共祖先。这里是情况1，左右子树有p和q，情况2是“中”就是p或者q，但情况1是把情况2包含了
- 递归函数的参数和返回值：返回值TreeNode，参数就是root，p，q
- 终止条件：如果root为空就返回null；如果root==p或者root==q就返回root，这就是发现了目标值了
- 单层递归的逻辑：左右中，先左，left=travelsal(root.left, p, q)，再右，right=travelsal(root.right, p, q)，然后是中，如果左右都不为空，此时root就是最近公共祖先，就return root，一直返回给根节点；如果left==null&&right!=null，就return right；如果left!=null&&right==null，就return left；如果左右都为空就返回null
- 为什么包含了情况2？假设q就是公共祖先，因为在终止条件中，如果root==q就把q返回了，下面就不去遍历了，就一直把q返回给到根节点了。那如果p不是q的子孙呢？这就是情况1了，那p就在根节点的另一边，另一边一直返回返回给到根节点，那么根节点就是最近公共祖先。这里不懂看视频16分钟开始
3.2 代码
// 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) { // 若未找到节点 p 或 q return null; }else if(left == null && right != null) { // 若找到一个节点 return right; }else if(left != null && right == null) { // 若找到一个节点 return left; }else { // 若找到两个节点 return root; } } }
