给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
思路:二叉搜索树的中序遍历结果是递增数列,我们可以把遍历的结果存入一个数组中,遍历该数组找到最小绝对差,但是开辟该数组需要额外存储空间,我们可以使用两个指针,分别执行当前结点和前一结点来更新最小绝对差
递归三要素
1.确定返回值和参数类型
中序遍历二叉树,更新minDiff值,无需返回值,返回值为void,参数为TreeNode
2.确定递归结束条件
if(cur==null) return;遍历到空结点停止
3.确定单层递归逻辑
如果pre!=null,说明当前不是遍历到第一个结点,求出两结点之间的插值,让当前结点成为上一结点 pre=cur;
代码参考:
class Solution {
int minDiff=Integer.MAX_VALUE;
TreeNode pre=null;
public int getMinimumDifference(TreeNode root) {
traversal(root);
return minDiff;
}
public void traversal(TreeNode cur){
if(cur==null) return;
traversal(cur.left);
if(pre!=null){
minDiff=Math.min(cur.val-pre.val,minDiff);
}
pre=cur;
traversal(cur.right);
}
}
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]
思路:本题跟上一题思路是一致的,中序遍历二叉树搜索树,用两个指针分别指向上一结点和当前结点
注意:因为树中可能不只一个众数,所以用List存储结果,用maxcount记录最大次数,count记录当前次数,如果MaxCount<count需要清空之前存的数,如果MaxCount==count,则总数有多个
if(MaxCount<count){
result.clear();
result.add(cur.val);
MaxCount=count;
}else if(MaxCount==count){
result.add(cur.val);
}
代码参考:
class Solution {
int MaxCount=0;
int count=1;
TreeNode pre=null;
List<Integer> result;
public int[] findMode(TreeNode root) {
result=new ArrayList<Integer>();
travel(root);
int[] result1= new int[result.size()];
for(int i=0;i<result.size();i++){
result1[i]=result.get(i);
}
return result1;
}
public void travel(TreeNode cur){
if(cur==null)return;
travel(cur.left);
if(pre!=null){
//如果不为第一个结点
if(pre.val==cur.val)count++;
if(pre.val!=cur.val)count=1;
}
//第一个结点的清空包含在内
if(MaxCount<count){
result.clear();
result.add(cur.val);
MaxCount=count;
}else if(MaxCount==count){
result.add(cur.val);
}
pre=cur;
travel(cur.right);
}
}
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 。
最近公共祖先的两种情况:
很容易忽略一个节点也可以是它自己的祖先的这种情况
递归三要素:
1.确定返回值和参数类型:
当我们找到其中一个结点时,就返回该结点,返回值类型为TreeNode,传入一颗树,需要寻找的两个结点
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
2.确定递归结束条件
找到其中一个结点时就返回(这里已经包括了当前结点为自己祖先的情况),如果遍历到叶节点则返回null,
3.单层递归逻辑
1)如果递归左右子树的返回值都不为空,显然当前结点为最近公共祖先,我们继续向上返回该结点
2)如果左右子树只有其中一个返回值不为空,那么这个返回值 就是最近公共祖先
寻找公共祖先,我们需要从下往上遍历,本题使用后序遍历
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null)return null;
//找到一个结点就返回该节点
if(root==q||root==p) 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)return right;
return left;
}
}