530.二叉搜索樹的最小絕對差

題目鏈接：530. 二叉搜索樹的最小絕對差

思路：二叉搜索樹的中序遍歷是有序的。根據二叉搜索樹的這個特性來解題。

class Solution {// 同樣利用二叉樹中序遍歷是一個有序數組。private List<Integer> list = new ArrayList<>();public int getMinimumDifference(TreeNode root) {int res = Integer.MAX_VALUE;inorder(root);for (int i = 0; i < list.size() - 1; i++) {int temp = list.get(i + 1) - list.get(i);res = Math.min(res, temp);}return res;}public void inorder(TreeNode node) {if (node == null) return;inorder(node.left);list.add(node.val);inorder(node.right);}
}

另一種解法，中序遍歷會有序遍歷BST的節點，遍歷過程中計算最小差值即可。

class Solution {public int getMinimumDifference(TreeNode root) {traverse(root);return res;}TreeNode prev = null;int res = Integer.MAX_VALUE;// 遍歷函數void traverse(TreeNode root) {if (root == null) {return;}traverse(root.left);// 中序遍歷位置if (prev != null) {res = Math.min(res, root.val - prev.val);}prev = root;traverse(root.right);}
}

---

501.二叉搜索樹中的眾數

題目鏈接：501. 二叉搜索樹中的眾數

思路：同樣利用二叉搜索樹的特性（二叉搜索樹中序遍歷是一個有序數組）。中序遞歸遍歷，如果當前節點與前一個節點值相同，則記錄count的值，如果count的值大于或者等于最大相同節點個數，就要更新結果。

class Solution {List<Integer> list = new ArrayList<>();int count; // 記錄當前節點元素的重復次數int maxCount; // 記錄最大相同節點個數TreeNode pre = null; // 指向前一個節點public int[] findMode(TreeNode root) {inorder(root);int[] res = new int[list.size()];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}public void inorder(TreeNode node) {if (node == null) return;inorder(node.left);// 如果是第一個節點，或者當前節點與前一個節點值不同if (pre == null || pre.val != node.val) {count = 1;} else {count++;}// 更新結果if (count > maxCount) {list.clear();list.add(node.val);maxCount = count;} else if (count == maxCount) {list.add(node.val);}pre = node;inorder(node.right);}
}

---

236. 二叉樹的最近公共祖先

題目鏈接：236. 二叉樹的最近公共祖先

思路：通過后序遞歸遍歷（因為要從下往上返回，所以要采用后序遍歷的順序）。先給出遞歸函數的定義：給該函數輸入三個參數 root，p，q，它會返回一個節點。根據定義，分情況討論進行解題。

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// base caseif (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);// 如果 p 和 q 都在以 root 為根的樹中，那么 left 和 right 一定分別是 p 和 qif (left != null && right != null) {return root;}// 如果 p 和 q 都不在以 root 為根的樹中，直接返回 nullif (left == null && right == null) {return null;}// 如果 p 和 q 只有一個存在于 root 為根的樹中，函數返回該節點return left == null ? right : left;}
}

---