目录
501.二叉搜索树中的众树
题目
代码（普通二叉树）
代码（中序递归二叉搜索树）
代码（中序迭代二叉搜索树）
236.二叉树的最近公共祖先
题目
代码（递归法）
235.二叉搜索树的最近公共祖先
题目
代码（迭代法）
代码（递归法）
501.二叉搜索树中的众树
题目
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]
代码（普通二叉树）
class Solution {
public int[] findMode(TreeNode root) {
Map<Integer,Integer> map = new HashMap<>();
List<Integer> result = new ArrayList<>();
if(root == null){
return result.stream().mapToInt(Integer::intValue).toArray(); //把列表转为数组
}
inOrder(root,map); //递归遍历二叉树，存到map中
int max = 0; //最大出现次数对应的key
int maxCount = 0; //最大的value（出现次数）
//遍历map，获取最大出现次数
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(entry.getValue() > maxCount){
maxCount = entry.getValue();
}
}
//遍历map，把map中value=maxCount的key都加到list中
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(entry.getValue() == maxCount){
result.add(entry.getKey());
}
}
return result.stream().mapToInt(Integer::intValue).toArray(); //返回数组
}
public void inOrder(TreeNode root,Map<Integer,Integer> map){
if(root == null){
return;
}
inOrder(root.left,map);
map.put(root.val,map.getOrDefault(root.val,0) + 1);
inOrder(root.right,map);
}
}代码（中序递归二叉搜索树）
class Solution {
List<Integer> list = new ArrayList<Integer>(); //存放结果
TreeNode pre = null;
int count = 0;
int maxCount = 0;
public int[] findMode(TreeNode root) {
inOrder(root); //中序递归遍历
return list.stream().mapToInt(Integer::intValue).toArray(); //返回数组
}
public void inOrder(TreeNode root){
//终止条件
if(root == null){
return;
}
//单层逻辑
inOrder(root.left); //左子树
//处理中间节点
if(pre == null || pre.val != root.val){
count = 1; //是第一个结点or前一个节点和当前节点值不同
}
else{
count++; //前一个节点和当前节点值相同
}
//如果count不变，list中不断加入
if(count == maxCount){
list.add(root.val);
}
//如果count更新为更大的值，重置list
if(count > maxCount){
maxCount = count; //更新最大出现次数
list.clear(); //清空列表
list.add(root.val); //把最大的值加入list
}
pre = root;
inOrder(root.right); //右子树
}
}代码（中序迭代二叉搜索树）
class Solution {
public int[] findMode(TreeNode root) {
List<Integer> list = new ArrayList<Integer>(); //存放结果
TreeNode pre = null;
int count = 0;
int maxCount = 0;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
//中序迭代二叉树
while(!stack.isEmpty() || cur != null){
//cur一直走到最左下
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(pre == null || pre.val != cur.val){
count = 1;
}
else{
count++;
}
//如果count不变，list中不断加入
if(count == maxCount){
list.add(cur.val);
}
//如果count更新为更大的值，重置list
if(count > maxCount){
maxCount = count; //更新最大出现次数
list.clear(); //清空列表
list.add(cur.val); //把最大的值加入list
}
pre = cur;
cur = cur.right;
}
return list.stream().mapToInt(Integer::intValue).toArray(); //返回数组
}
}236.二叉树的最近公共祖先
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
代码（后序递归法搜索整个树）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//终止条件
if(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); //右子树
//中间节点
if(left == null && right == null){
return null;
}
else if(left == null && right != null){
return right;
}
else if(left != null && right == null){
return left;
}
else{
return root;
}
}
}235.二叉搜索树的最近公共祖先
题目
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。
代码（迭代法）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//从上往下遍历，第一个满足值在[p,q]区间内的节点，就是最近公共祖先。
while(true){
//root太大，往左边走
if(root.val > p.val && root.val > q.val){
root = root.left;
}
//root太小，往右边走
else if(root.val < p.val && root.val < q.val){
root = root.right;
}
//root在[p,q]区间内，找到了第一个满足条件的就是最近公共祖先
else{
break;
}
}
return root;
}
}代码（递归法搜索一条边）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//到左子树找公共祖先
if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left,p,q); //直接走左子树，右子树不要了
}
//到右子树找公共祖先
if(root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right,p,q); //直接走右子树，左子树不要了
}
return root; //当前节点区间[p,q]之间，直接返回root
}
}