#Java #二叉树 #双指针
开源学习资料
Feeling and experiences：
二叉搜索树的最小绝对差：力扣题目链接
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
之前递归搜索树写多了，导致首先想到的方法 是把每个节点与左右子树值的差返回给上一级作比较。
但是该题目更好的做法是用中序遍历：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int minNode; //记录答案
int pre; //用来记录前一个节点
public int getMinimumDifference(TreeNode root) {
//初始化最大值
minNode = Integer.MAX_VALUE;
//初始化为-1；
pre = -1;
dfs(root);
return minNode;
}
public void dfs(TreeNode node){
if(node == null){
return;
}
//利用中序遍历
//先遍历左子树
dfs(node.left);
//用pre记录前一个节点的值
if(pre == -1){
pre = node.val;
}else{
minNode = Math.min(minNode , node.val - pre);
pre = node.val;
}
//遍历右子树
dfs(node.right);
}
}整体思路很简单：就是一个pre指针记录上一个节点的值，与当前值进行相减之后，与minNode中存储的结果作比较（minNode中肯定存放的是更小的值），这样可以更新其结果，遍历完得到最终的结果。
图解如下：
用栈模拟，迭代法：
class Solution {
public int getMinimumDifference(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
int result = Integer.MAX_VALUE;
if(root != null)
stack.add(root);
while(!stack.isEmpty()){
TreeNode curr = stack.peek();
if(curr != null){
stack.pop();
if(curr.right != null)
stack.add(curr.right);
stack.add(curr);
stack.add(null);
if(curr.left != null)
stack.add(curr.left);
}else{
stack.pop();
TreeNode temp = stack.pop();
if(pre != null)
result = Math.min(result, temp.val - pre.val);
pre = temp;
}
}
return result;
}
}
二叉搜索树中的众数：力扣题目链接
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
我根据上一个题的思路写了一个解法：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//该树是一个二叉搜索树
List<Integer> list = new ArrayList<>();
int pre = -1;
int preCount = 0;
int maxCount = 0;
public int[] findMode(TreeNode root) {
dfs(root);
addMore(pre,preCount);
int [] res = new int[list.size()];
for(int i =0;i<list.size();i++){
res[i] = list.get(i);
}
return res;
}
public void dfs(TreeNode node){
if(node == null){
return;
}
dfs(node.left);
if(pre == -1 || pre != node.val){
addMore(pre,preCount);
pre = node.val;
preCount = 1;
}else{
preCount++;
}
dfs(node.right);
}
public void addMore(int value,int count){
if(count > maxCount){
maxCount = count;
list.clear();
if(value != -1)
list.add(value);
}else if(count == maxCount && value != -1){
list.add(value);
}
}
}不过，这段代码不能处理以下测试：
更改后的代码：
class Solution {
ArrayList<Integer> resList;
int maxCount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root) {
resList = new ArrayList<>();
maxCount = 0;
count = 0;
pre = null;
findMode1(root);
int[] res = new int[resList.size()];
for (int i = 0; i < resList.size(); i++) {
res[i] = resList.get(i);
}
return res;
}
public void findMode1(TreeNode root) {
if (root == null) {
return;
}
findMode1(root.left);
int rootValue = root.val;
// 计数
if (pre == null || rootValue != pre.val) {
count = 1;
} else {
count++;
}
// 更新结果以及maxCount
if (count > maxCount) {
resList.clear();
resList.add(rootValue);
maxCount = count;
} else if (count == maxCount) {
resList.add(rootValue);
}
pre = root;
findMode1(root.right);
}
}
二叉树的最近公共祖先：力扣题目链接
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
用后序遍历，从后往前找！
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || 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) { // 若未找到节点 p 或 q
return null;
}else if(left == null && right != null) { // 若找到一个节点
return right;
}else if(left != null && right == null) { // 若找到一个节点
return left;
}else { // 若找到两个节点
return root;
}
}
}
莫思身外无穷事，
且尽生前有限杯。
Fighting！
