530.二叉搜索树的最小绝对差
题目链接/文章讲解： 代码随想录视频讲解：二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差_哔哩哔哩_bilibili
注意是二叉搜索树，二叉搜索树可是有序的。
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
用递归
Java代码：
class Solution {
//递归
TreeNode pre;//记录上供遍历的节点
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root == null) return 0;
traversal(root);
return result;
}
public void traversal(TreeNode root){
//中序遍历 二叉搜索树 左 < 中 《 右
//从小到大的有序数组
if(root == null) return;
//左侧
traversal(root.left);
//右侧
if(pre != null){
result = Math.min(result, root.val - pre.val);
}
pre = root;
//右
traversal(root.right);
}
}
class Solution{
TreeNode pre;
Stack<TreeNode> stack;
public int getMinimumDifference(TreeNode root){
//迭代法
if(root == null) return 0;
stack = new Stack<>();
TreeNode cur = root;
int result = Integer.MAX_VALUE;
while(cur != null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);//把访问的节点放入栈
cur = cur.left;//左
} else{
cur = stack.pop();
if(pre != null){
result = Math.min(result, cur.val - pre.val);
}
pre = cur;
cur = cur.right;
}
}
return result;
}
}501.二叉搜索树众数
视频讲解：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数_哔哩哔哩_bilibili
做了不少二叉树 做到这里我突然感觉自己对二叉树的理解不透彻 搞懂二叉树对于节点移动的逻辑 这道题要求输出一个众数的集合 所以要对输出上有所要求
之后仔细想 其实二叉树就是四种遍历 层序遍历 前中后序遍历
class Solution{
ArrayList<Integer> reslist;
int maxcount;
int count;
TreeNode pre;
public int[] findMode(TreeNode root){
reslist = new ArrayList<>();
maxcount = 0;
count = 0;
findMode1(root);
int[] ans = new int[reslist.size()];
for(int i = 0; i < reslist.size(); i++){
ans[i] = reslist.get(i);
}
return ans;
}
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);
}
}
class Solution{
public int[] findMode(TreeNode root){
if(root == null) return null;
TreeNode pre = null;
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
int maxcount = 0;
int count = 0;
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{//到叶子结点了
cur = stack.pop();
//计数
if(pre == null || cur.val != pre.val){
count = 1;
}else{
count++;
}
//更新结果
if(count > maxcount){
maxcount = count;
result.clear();
result.add(cur.val);
}else if(count == maxcount){
result.add(cur.val);
}
pre = cur;
cur = cur.right;
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}
236. 二叉树的最近公共祖先
题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）
讲解链接：代码随想录
这道题有点难度 但是也没关系 看看讲解
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
/********************************************************************************\重点：
-
求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
-
在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
-
要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
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;
}
}
}
class Solution{
//迭代
public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
int max = Integer.MAX_VALUE;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root, pre = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(cur.right == null || cur.right == pre){
//p/q是 中/左 或者 中/右 返回中间节点
if(cur == p || cur == q){
if((cur.left != null && cur.left.val == max) || (cur.right != null && cur.right.val == max)){
return cur;
}
cur.val = max;
}
//p/q是 左/右 返回中
if(cur.left != null && cur.left.val == max && cur.right != null && cur.right.val ==max){
return cur;
}
//MAX_VALUE向上传递
if((cur.left != null && cur.left.val == max) || (cur.right != null && cur.right.val == max)){
cur.val = max;
}
pre = cur;
cur = null;
}else{
stack.push(cur);
cur = cur.right;
}
}
return null;
}
}day18 去看看算法课
标签：pre,第十八天,right,TreeNode,cur,二叉,搜索,null,root From： https://blog.csdn.net/chengooooooo/article/details/144471898