Rubyr代码随想录算法训练营第21天|● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

Leetcode  530.二叉搜索树的最小绝对差 

1)通过中序遍历来记录前一个节点与当前节点的绝对差

class Solution {int min = Integer.MAX_VALUE;TreeNode pre = null;public int getMinimumDifference(TreeNode root) {tranverse(root);return min;}public void tranverse(TreeNode root) {if (root == null) {return;}tranverse(root.left);//find the min absolute diffirence at hereif (pre != null) {min = Math.min(min, Math.abs(root.val - pre.val));}pre = root;tranverse(root.right);}
}

Leetcode 501.二叉搜索树中的众数 

1)通过中序遍历来找众数，因为是递增序列，如果有相同的会在一起

2）在写查找众数时，先判断当前节点的值和之前记录的值是否相等，相等 count = count + 1; 否则count = 1；

3) 在比较当前的count和maxCount, 如果相等，就加入到arraylist里；不相等说明要更新众数，清楚list之前的众数，添加新的众数。

class Solution {int currCount = 0;int maxCount = 0;int currentVal;List<Integer> res = new ArrayList<>();public int[] findMode(TreeNode root) {tranverse(root);int[] result = new int[res.size()];for (int i = 0; i < res.size(); i++) {result[i] = res.get(i);}return result;}public void tranverse(TreeNode node) {if (node == null) {return;}tranverse(node.left);currCount = (node.val == currentVal) ? currCount + 1 : 1 ;if (currCount == maxCount) {res.add(node.val);} else if (currCount > maxCount) {res.clear();maxCount = currCount;res.add(node.val);}currentVal = node.val;tranverse(node.right);}
}

Leetcode 236. 二叉树的最近公共祖先  

1）两个节点的最近公共祖先其实就是这两个节点向根节点的 ‘ 延长线 ’ 的交汇点

2）如果一个节点能够在它的左右子树中分别找到 p 和 q，则该节点为 LCA 节点，也包括该节点自身

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;}if (root.val == p.val || root.val == q.val) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left != null && right != null) {return root;} return (left != null) ? left : right;}}