二叉树最小绝对差
双指针法
private TreeNode pre;
public int getMinimumDifference(TreeNode root) {
if(root == null) {
return Integer.MAX_VALUE;
}
int a = getMinimumDifference(root.left);
int c = Integer.MAX_VALUE;
if(pre != null) {
c = root.val - pre.val;
}
pre = root;
int b = getMinimumDifference(root.right);
return Math.min(c,Math.min(a,b));
}
二叉搜索树中的众数
private List<Integer> res = new ArrayList();
private int count;
private int maxCount;
private TreeNode pre;
public int[] findMode(TreeNode root) {
find(root);
return res.stream().mapToInt(Integer::intValue).toArray();
}
private void find(TreeNode root) {
if(root == null) {
return;
}
find(root.left);
if(pre == null) {
count = 1;
} else if (pre.val == root.val) {
count++;
} else {
count=1;
}
pre = root;
if(maxCount == count) {
res.add(root.val);
} else if(maxCount < count) {
res.clear();
res.add(root.val);
maxCount = count;
}
find(root.right);
}
二叉树最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root ==p || root == q) {
return root;
}
TreeNode l = lowestCommonAncestor(root.left,p,q);
TreeNode r = lowestCommonAncestor(root.right,p,q);
if(l == null) {
return r;
} else if(r== null) {
return l;
}else if(r != null) {
return root;
}
return null;
}
