本文主要是介绍双非本科准备秋招（23.1）—— 力扣二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、501. 二叉搜索树中的众数
中序遍历得到有序数组和最高频次，然后再次遍历有序数组。
可以改进一下，只遍历一次：每次更新最大值的时候，顺便清空数组，这样最后数组里一定都是最高频次的元素了。
class Solution {List<Integer> list = new ArrayList<>();int cnt = 1;TreeNode pre = null;int maxValue = 0;public int[] findMode(TreeNode root) {inOrder(root);return list.stream().mapToInt(Integer::intValue).toArray();}void inOrder(TreeNode root){if(root == null) return ;inOrder(root.left);if(pre != null){if(pre.val == root.val){cnt++;}else{//不相等，说明遇到新元素cnt = 1;}}pre = root;// maxValue = Math.max(maxValue, cnt);if(cnt == maxValue){list.add(root.val);}else if(cnt > maxValue){maxValue = cnt;list.clear();list.add(root.val);}inOrder(root.right);}
}2、236. 二叉树的最近公共祖先
核心思想就是层层返回拥有p或者q的节点。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return postOrder(root, p, q);}TreeNode postOrder(TreeNode root, TreeNode p, TreeNode q){if(root == null) return root;if(root == p || root == q) return root;TreeNode left = postOrder(root.left, p, q);TreeNode right = postOrder(root.right, p, q);if(left != null && right != null) return root;else if(left == null && right != null) return right;else if(left != null && right == null) return left;else return null; }
}3、235. 二叉搜索树的最近公共祖先
根据二叉搜索树的特点，使用前序遍历，只要当前节点的值在p、q之间，就代表当前节点是二叉搜索树的最近公共祖先。
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {LinkedList<TreeNode> stack = new LinkedList<>();if(p.val > q.val){TreeNode x = q;q = p;p = x;}while(root != null || !stack.isEmpty()){if(root != null){if(root.val >= p.val && root.val <= q.val){return root;}stack.push(root);root = root.left;}else{TreeNode t = stack.pop();root = t.right;}}return null;}
}这篇关于双非本科准备秋招（23.1）—— 力扣二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
