Day18--二叉树--530. 二叉搜索树的最小绝对差，501. 二叉搜索树中的众数，236. 二叉树的最近公共祖先

思路：

递归法，不用额外辅助方法，每层都要把min往上传，然后比较

// 递归法，不用额外辅助方法，每层都要把min往上传，然后比较
class Solution {private int min = Integer.MAX_VALUE;private TreeNode pre;public int getMinimumDifference(TreeNode root) {// 中序遍历// 左if (root.left != null) {min = Math.min(min, getMinimumDifference(root.left));}// 根if (pre != null) {min = Math.min(min, root.val - pre.val);}pre = root;// 右if (root.right != null) {min = Math.min(min, getMinimumDifference(root.right));}return min;}
}

思路：

递归法，额外辅助方法

class Solution {TreeNode pre; // 记录上一个遍历的结点int res = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {// 最少有2个结点，不用判断root==null的情况// res是定义在全局的，所以递归方法不需要返回值traversal(root);return res;}public void traversal(TreeNode cur) {if (cur == null)return;// 左traversal(cur.left);// 中if (pre != null) {res = Math.min(res, cur.val - pre.val);}pre = cur;// 右traversal(cur.right);}
}

思路：

普通迭代法

//  迭代法：中序遍历
class Solution {public int getMinimumDifference(TreeNode root) {// 因为是迭代法，定义在这里，就可以在while循环里面“当成全局”用了。TreeNode pre = null;Deque<TreeNode> stack = new ArrayDeque<>();int res = Integer.MAX_VALUE;TreeNode cur = root;while (cur != null || !stack.isEmpty()) {// 指针来访问节点，访问到最底层if (cur != null) {// 将访问的节点放进栈stack.push(cur);// 左cur = cur.left;} else {// 中cur = stack.pop();if (pre != null) {res = Math.min(res, cur.val - pre.val);}pre = cur;// 右cur = cur.right;}}return res;}
}

思路：

迭代法（中序遍历的迭代法不是那么好写的）

//  统一的迭代法，中序遍历
class Solution {public int getMinimumDifference(TreeNode root) {// 只有LinkedList能存null指针，ArrayDeque不行// Deque<TreeNode> stack = new LinkedList<>();// 这题里面，使用LinkedList会超时，所以只能用Stack类。但是Stack类已经过时了，在实际开发中并不推荐Stack<TreeNode> stack = new Stack<>();// 因为是迭代法，定义在这里，就可以在while循环里面“当成全局”用了。TreeNode pre = null;int result = Integer.MAX_VALUE;if (root != null){stack.add(root);}// 中序遍历（左中右），由于栈先入后出，反序（右中左）while (!stack.isEmpty()) {TreeNode cur = stack.peek();if (cur != null) {stack.pop();// 右if (cur.right != null){stack.add(cur.right);}// 中（先用null标记）stack.add(cur);stack.add(null);// 左if (cur.left != null){stack.add(cur.left);}} else { // 中（遇到null再处理）// 先弹出nullstack.pop();cur = stack.pop();if (pre != null){result = Math.min(result, cur.val - pre.val);}pre = cur;}}return result;}
}

思路：

暴力解法：当成普通二叉树来统计。先遍历一遍二叉树放进map，再遍历一遍map得到最大值，再遍历一遍map看看谁的频率等于最大值

//  暴力解法：当成普通二叉树来统计。先遍历一遍二叉树放进map，再遍历一遍map得到最大值，再遍历一遍map看看谁的频率等于最大值
class Solution {Map<Integer, Integer> map = new HashMap<>();public int[] findMode(TreeNode root) {// 先遍历一遍二叉树放进mapinTravel(root);// 再遍历一遍map得到最大值，int max = Integer.MIN_VALUE;for (var e : map.entrySet()) {if (e.getValue() > max) {max = e.getValue();}}// 再遍历一遍map看看谁的频率等于最大值List<Integer> list = new ArrayList<>();for (var e : map.entrySet()) {if (e.getValue() == max) {list.add(e.getKey());}}// 最后把list转成int[]输出return list.stream().mapToInt(Integer::intValue).toArray();}// 递归，中序遍历private void inTravel(TreeNode node) {if (node.left != null) {inTravel(node.left);}map.put(node.val, map.getOrDefault(node.val, 0) + 1);if (node.right != null) {inTravel(node.right);}}
}

思路：

中序递归法。使用pre，count和maxCount

//  中序递归法。使用pre，count和maxCount
class Solution {List<Integer> res = new ArrayList<>();TreeNode pre = null;int maxCount = 0;int count = 0;public int[] findMode(TreeNode root) {if (root == null) {return new int[0];}inorderTravel(root);// 将res转换为int[]return res.stream().mapToInt(Integer::intValue).toArray();}private void inorderTravel(TreeNode node) {// 左if (node.left != null) {inorderTravel(node.left);}// 中// 计数if (pre == null || pre.val != node.val) {count = 1;} else {count++;}// 更新count和maxCountif (count == maxCount) {res.add(node.val);} else if (count > maxCount) {maxCount = count;// 如果maxCount变了，就是众数变了。之前结果集里面的数都不是众数了，要清空res.clear();res.add(node.val);}pre = node;// 右if (node.right != null) {inorderTravel(node.right);}}
}

思路：

迭代法，中序遍历

ps：如果习惯用迭代法中序遍历的，要熟练写其中一种方法，不要普通迭代法和统一迭代法都试试，除非用得非常熟练。不然这两个方法容易混。

//  迭代法，中序遍历
class Solution {public int[] findMode(TreeNode root) {if (root == null) {return new int[0];}// 初始化“全局变量”，while遍历的时候要用的List<Integer> res = new ArrayList<>();TreeNode pre = null;int maxCount = 0;int count = 0;// 迭代遍历要用的Deque<TreeNode> stack = new ArrayDeque<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {// 把“中”压栈，一直往下往左边找stack.push(cur);// 左cur = cur.left;} else {// 弹出“中”cur = stack.pop();// 中// 计数if (pre == null || pre.val != cur.val) {count = 1;} else {count++;}// 更新count和maxCountif (count == maxCount) {res.add(cur.val);} else if (count > maxCount) {maxCount = count;// 如果maxCount变了，就是众数变了。之前结果集里面的数都不是众数了，要清空res.clear();res.add(cur.val);}pre = cur;// 右cur = cur.right;}}// 将res转换为int[]return res.stream().mapToInt(Integer::intValue).toArray();}}

《代码随想录》：

后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。

思路：递归法，后序遍历

//  递归法，后序遍历
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 如果是p或者q，返回给上一层；如果是null，也返回null// 如果子结点有p或者q，自己又是p或者q之一，返回自己就是返回祖先了if (root == q || root == p || root == null) {return root;}// 递归，后序TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);// 如果左右子树遍历之后，拿回来了值，那肯定本节点就是祖先了。if (left != null && right != null) {return root;}// 返回有节点的那边，返回那个节点。if (left == null && right != null) {return right;} else if (left != null && right == null) {return left;} else {// 这里就剩下，(left == null && right != null)的情况了，但是不能用else if，会报错。return null;}}
}