530.二叉搜索树的最小绝对差
题目链接：530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）
思路
题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。
注意是二叉搜索树，二叉搜索树可是有序的。
遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。
方法一：可以把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值了。
方法二：双指针，用一个 pre 节点记录一下 cur 节点的前一个节点。然后求差值即可通过一次遍历直接得到结果。
代码
1 class Solution {
2 TreeNode pre;// 记录上一个遍历的结点
3 int result = Integer.MAX_VALUE;
4 public int getMinimumDifference(TreeNode root) {
5 if(root==null)return 0;
6 traversal(root);
7 return result;
8 }
9 public void traversal(TreeNode root){
10 if(root==null)return;
11 //左
12 traversal(root.left);
13 //中
14 if(pre!=null){
15 result = Math.min(result,root.val-pre.val);
16 }
17 pre = root;
18 //右
19 traversal(root.right);
20 }
21 }
1 // 迭代法-中序遍历
2 class Solution {
3 TreeNode pre;
4 Stack<TreeNode> stack;
5 public int getMinimumDifference(TreeNode root) {
6 if (root == null) return 0;
7 stack = new Stack<>();
8 TreeNode cur = root;
9 int result = Integer.MAX_VALUE;
10 while (cur != null || !stack.isEmpty()) {
11 if (cur != null) {
12 stack.push(cur); // 将访问的节点放进栈
13 cur = cur.left; // 左
14 }else {
15 cur = stack.pop();
16 if (pre != null) { // 中
17 result = Math.min(result, cur.val - pre.val);
18 }
19 pre = cur;
20 cur = cur.right; // 右
21 }
22 }
23 return result;
24 }
25 }
总结
遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。
同时要学会在递归遍历的过程中如何记录前后两个指针，这也是一个小技巧，学会了还是很受用的。
501.二叉搜索树中的众数
题目链接：501. 二叉搜索树中的众数 - 力扣（LeetCode）
思路
使用pre指针和cur指针的技巧，步骤如下。
- pre=null时，cur遍历到了左子树的叶子结点，此时cur所出现的次数为1
- 若pre.val=cur.val时，证明前向结点值后向结点值相等，即cur所出现次数+1
- 否则pre.val!=cur.val，证明前向结点值和后向结点值不等，即cur出现1次
- 判断该结点所出现的次数是否等于maxCount，是的话就加入list
- 若不是则更新maxCount，以及更新list
代码
// 中序遍历-不使用额外空间，利用二叉搜索树特性
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);
}
}
// 迭代法
class Solution {
public int[] findMode(TreeNode root) {
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
int maxCount = 0;
int count = 0;
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur =cur.left;
}else {
cur = stack.pop();
// 计数
if (pre == null || cur.val != pre.val) {
count = 1;
}else {
count++;
}
// 更新结果
if (count > maxCount) {
maxCount = count;
result.clear();
result.add(cur.val);
}else if (count == maxCount) {
result.add(cur.val);
}
pre = cur;
cur = cur.right;
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}
扩展
如果本题不是二叉搜索数，那可采用暴力法，把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。
使用暴力法时，注意以下细节。
- 用前中后序哪种遍历也不重要，因为就是要全遍历一遍，怎么个遍历法都行，层序遍历都没毛病！
- 要把map转化数组即
List<Map.Entry<Integer, Integer>>，再进行排序。
代码
1 class Solution {
2 public int[] findMode(TreeNode root) {
3 Map<Integer, Integer> map = new HashMap<>();
4 List<Integer> list = new ArrayList<>();
5 if (root == null) return list.stream().mapToInt(Integer::intValue).toArray();
6 // 获得频率 Map
7 searchBST(root, map);
8 List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
9 .sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
10 .collect(Collectors.toList());
11 list.add(mapList.get(0).getKey());
12 // 把频率最高的加入 list
13 for (int i = 1; i < mapList.size(); i++) {
14 if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {
15 list.add(mapList.get(i).getKey());
16 } else {
17 break;
18 }
19 }
20 return list.stream().mapToInt(Integer::intValue).toArray();
21 }
22
23 void searchBST(TreeNode curr, Map<Integer, Integer> map) {
24 if (curr == null) return;
25 map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);
26 searchBST(curr.left, map);
27 searchBST(curr.right, map);
28 }
29
30 }
236. 二叉树的最近公共祖先
题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）
思路
遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。
那么二叉树如何可以自底向上查找呢？
回溯啊，二叉树回溯的过程就是从低到上。
后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。
接下来就看如何判断一个节点是节点q和节点p的公共祖先呢。
情况一：如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。
判断逻辑是 如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先。
情况二，就是节点本身p(q)，它拥有一个子孙节点q(p)。其实情况一 和 情况二 代码实现过程都是一样的，也可以说，实现情况一的逻辑，顺便包含了情况二。
因为遇到 q 或者 p 就返回，这样也包含了 q 或者 p 本身就是 公共祖先的情况。
代码
1 class Solution {
2 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
3 if (root == null || root == p || root == q) { // 递归结束条件
4 return root;
5 }
6
7 // 后序遍历
8 TreeNode left = lowestCommonAncestor(root.left, p, q);
9 TreeNode right = lowestCommonAncestor(root.right, p, q);
10
11 if(left == null && right == null) { // 若未找到节点 p 或 q
12 return null;
13 }else if(left == null && right != null) { // 若找到一个节点
14 return right;
15 }else if(left != null && right == null) { // 若找到一个节点
16 return left;
17 }else { // 若找到两个节点
18 return root;
19 }
20 }
21 }
总结
-
求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
-
在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
-
要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
可以说这里每一步，都是有难度的，都需要对二叉树，递归和回溯有一定的理解。
本题没有给出迭代法，因为迭代法不适合模拟回溯的过程。理解递归的解法就够了。
标签：pre,遍历,TreeNode,cur,随想录,二叉,搜索,null,root From： https://www.cnblogs.com/xpp3/p/17146579.html