西安俄语网站建设,网站标题没有排名,建立网站步骤,图片模板网站二叉搜索树的最小绝对差
题目详细#xff1a;LeetCode.530
这道题使我第一次了解到二叉树的双指针遍历法#xff0c;详细可以先查看卡哥的讲解视频#xff1a;《代码随想录 — 二叉搜索树中的众数》
利用二叉搜索树的特点#xff1a;
中序遍历二叉搜索树得到一个有序序…二叉搜索树的最小绝对差
题目详细LeetCode.530
这道题使我第一次了解到二叉树的双指针遍历法详细可以先查看卡哥的讲解视频《代码随想录 — 二叉搜索树中的众数》
利用二叉搜索树的特点
中序遍历二叉搜索树得到一个有序序列计算序列中相邻的每一个数的差值记录最小绝对值差
但我们可以发现如果我们可以在遍历过程中去计算相邻的两个数的差值那么速度将提升很多对于序列是否有序这一点似乎并不是特别重要只是二叉搜索树赋予了它这一特点。
那么我们可以利用双指针法
定义一个指针 pre 指向当前节点的前一个节点按照左中右的顺序深度优先遍历树的节点 若 pre 为空则说明当前节点为叶子节点不存在前一个节点若 pre 不为空则计算前一个节点与当前节点的绝对差值利用全局变量记录一个最小值结果 注意更新前一个节点 pre cur
Java解法递归
class Solution {public int ans Integer.MAX_VALUE;public TreeNode pre null;public int getMinimumDifference(TreeNode root) {this.dfs(root);return ans;}public void dfs(TreeNode cur){if(null cur) return;this.dfs(cur.left);if(null ! this.pre){ans Math.min(ans, Math.abs(pre.val - cur.val));}this.pre cur;this.dfs(cur.right);}
}二叉搜索树中的众数
题目详细LeetCode.501
传统的暴力解法有
解法一得到中序遍历序列后统计序列中出现次数最多的数字解法二遍历一次二叉树记录最高出现频率再中序遍历一次二叉树将出现频率等于最高出现频率的数字加入结果集这种方法都相当于需要遍历两次二叉树效率较低这里就不多赘述了
那么我们能否利用二叉搜索树中序遍历有序的特点在遍历过程中就统计最高出现频率的数字呢
在经过上一题了解二叉搜索树中双指针法的应用后在遇到二叉搜索树相关问题时就又多了一种解题思路中序遍历双指针法
定义两个变量times 记录当前数字的出现频率max_times 记录最高出现频率众所周知利用二叉搜索树的特点通过中序遍历可以得到一个有序序列因为中序遍历结果是有序序列所以数字一定是递增地连续地出现的那么利用双指针法 在递归中序遍历二叉树的过程中通过比较 pre 和 cur 的数值记录当前数字的出现频率比较当前出现频率和最高出现频率 若当前出现频率等于最高出现频率那么将数字加入结果集若当前出现频率高于已知的最高出现频率那么更新最高出现频率并清空当前结果集后再加入当前数字
Java解法中序遍历双指针法
class Solution {public ListInteger ans new ArrayList();public int max_times 1, times 1;public TreeNode pre null;public int[] findMode(TreeNode root) {this.dfs(root);return ans.stream().mapToInt(Integer::valueOf).toArray();}public void dfs(TreeNode cur){if(null cur) return ;// 左this.dfs(cur.left);// 中// 记录当前数字的出现频率if(null ! this.pre){if(cur.val this.pre.val){this.times;}else{this.times 1;}}if(this.times this.max_times){// 如果出现频率等于最高频率那么将数字加入结果集this.ans.add(cur.val);}else if(this.times this.max_times){// 如果出现频率高于已知的最高频率那么更新最高频率并清空当前结果集后再加入新的数字this.max_times this.times;this.ans.clear();this.ans.add(cur.val);}this.pre cur;//右this.dfs(cur.right);}
}二叉树的最近公共祖先
题目详细LeetCode.236
由题可知
所有节点的值都是唯一的p、q 均存在于给定的二叉树中一个节点也可以是它自己的祖先
所以我们可以先分析当前节点为最近公共祖先的情况有哪些也就是如何判断该节点是否是p、q的最近公共祖先
情况一 p 和 q 分别在左子树和右子树那么当前节点即为最近公共祖先直接返回 root情况二在右子树中找不到 p 或 q right null 那么说明 p 和 q 应都在左子树上返回 left在左子树中继续寻找情况三在左子树中找不到 p 或 q left null 那么说明 p 和 q 应都在右子树上返回 right在右子树中继续寻找
若我们基于深度优先遍历的递归算法进行解题那么还会出现一种情况
假如当 p 与当前节点相同时p root那么 q 必然只能分布在其子树中所以当前节点即为最近公共祖先同理可得当q root的情况。
通过分析最近公共祖先的三种基本情况可知解题的关键在于递归分析节点 p 和 q 在每一个节点的左右子树分布情况所以我们可以利用递归算法优先对当前节点的左右子树进行深度优先遍历通过左右子树的返回结果来确定当前节点是否为最近公共祖先。
Java解法递归
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root null || p root || q root)return root;TreeNode left lowestCommonAncestor(root.left,p,q);TreeNode right lowestCommonAncestor(root.right,p,q);return (right null) ? left : (left null) ? right : root;}
}
