【算法第十七天8.1】530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先

这篇具有很好参考价值的文章主要介绍了【算法第十七天8.1】530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链接力扣530-二叉搜索树的最小绝对差

思路

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为null时,需要开始弹出
                cur = stack.pop(); 
                if (pre != null) { // 中
                    result = Math.min(result, cur.val - pre.val);
                }
                // 把当前处理完的节点 作为 前驱节点
                pre = cur;
                // 处理完后的节点,需要找下一个节点
                cur = cur.right; // 右
            }
        }
        return result;
    }
}

链接力扣501-二叉搜索树中的众数

思路

class Solution {
	public int[] findMode(TreeNode root) {
		Map<Integer, Integer> map = new HashMap<>();
		List<Integer> list = new ArrayList<>();
		if (root == null) return list.stream().mapToInt(Integer::intValue).toArray();
		// 获得频率 Map
		searchBST(root, map);
		List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
				.sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
				.collect(Collectors.toList());
		list.add(mapList.get(0).getKey());
		// 把频率最高的加入 list
		for (int i = 1; i < mapList.size(); i++) {
			if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {
				list.add(mapList.get(i).getKey());
			} else {
				break;
			}
		}
		return list.stream().mapToInt(Integer::intValue).toArray();
	}

	void searchBST(TreeNode curr, Map<Integer, Integer> map) {
		if (curr == null) return;
		map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);
		searchBST(curr.left, map);
		searchBST(curr.right, map);
	}
}

链接力扣236.二叉树的最近公共祖先

思路文章来源地址https://www.toymoban.com/news/detail-624362.html

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) return left;
        else if(left == null &&right != null ) return right;
        else if(left == null && right == null) return null;
        else return root;
    }
}

到了这里,关于【算法第十七天8.1】530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法第十七天-构造有效字符串的最少插入数

    考虑abc的个数 假设答案有n个\\\"abc\\\"组成,那么需要插入的字符个数为 3 ∗ n − l e n ( s ) 3*n - len(s) 3 ∗ n − l e n ( s ) 。 对于相邻的两个字符x和y(x在y左侧): 如果 x y xy x y ,那么x和y可以在同一个\\\"abc\\\"内,否则一定不在; 如果 x ≥ y xge y x ≥ y ,那么x和y一定不可以在同一个

    2024年01月17日
    浏览(48)
  • 【力扣刷题 | 第十七天】

    目录 前言: 55. 跳跃游戏 - 力扣(LeetCode) 45. 跳跃游戏 II - 力扣(LeetCode) 总结:         今天两道类型都是贪心算法,希望可以有所收获 给定一个非负整数数组  nums  ,你最初位于数组的  第一个下标  。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断

    2024年02月15日
    浏览(45)
  • 学习Android的第十七天

    目录 Android ListView 添加插入数据 添加记录 在指定位置插入数据 Android ListView 删除数据 ListView 删除数据 ListView 清空数据 Android ListView 更改数据 ListView 数据更新 Android ListView 查询数据 ListView 数据查询 我们在顶部添加一个按钮,每次点击添加一条记录,并且数据为空时提示用户

    2024年02月22日
    浏览(49)
  • 30天精通Nodejs--第十七天:express-路由配置

    上篇文章我们简单介绍了express的基础用法,包括express的安装、创建路由及项目启动,对express有了一个基础的了解,这篇开始我们将详细介绍express的一些高级用法。 本篇文章介绍express的路由配置的用法。 上篇文章中我们在hello world中写了一个简单的get请求,除了get请求方式

    2024年01月22日
    浏览(46)
  • python爬虫-------urllib代理和代理池(第十七天)

    🎈🎈作者主页: 喔的嘛呀🎈🎈 🎈🎈所属专栏:python爬虫学习🎈🎈 ✨✨谢谢大家捧场,祝屏幕前的小伙伴们每天都有好运相伴左右,一定要天天开心哦!✨✨  嗨嗨嗨,兄弟姐妹们。我是喔的嘛呀。今天的学习内容是:爬虫 urllib代理和代理池 目录 一、爬虫 urllib——代理

    2024年04月14日
    浏览(42)
  • 学习Python第十七天:用python构建一个SSH僵尸网络

    在上一节我们已经创建了一个用来搜寻目标的端口扫描程序,选择可以开始利用这些服务中的漏洞了。Morris蠕虫有三种攻击方式,其中之一就是用常见的用户名和密码尝试登录RSH服务,RSH是1988年问世的,他为系统管理员提供了一种很棒的远程连接一台机器,并能在主机运行一

    2024年04月14日
    浏览(53)
  • 考研算法第十三天:二叉排序树 【二叉排序树的插入和遍历】

    这道题很妙。题目给的二叉排序树好像没学过其实就是二叉查找树。然后这道题主要的就是思路     1.先找到那个要删除节点所在处     2.找到之后处理分三种情况     删除的节点是叶节点,直接删除即可     删除的节点只有右节点或者左节点 将左节点或者右节点删除即可

    2024年02月05日
    浏览(49)
  • 算法刷题Day 21 二叉搜索树的最小绝对差+二叉搜索树中的众数+二叉树的最近公共祖先

    递归 递归中保存前一个节点的指针的方法,需要再学习,巩固一下 迭代 一下子就想到的方法:遍历一遍二叉搜索树,把各个节点的值存进哈希表里(节点值——键,出现频率——值),再遍历哈希表找众数 一般方法 既然是二叉搜索树,中序遍历就是有序的。有序的话,我

    2024年02月16日
    浏览(45)
  • 面试算法53:二叉搜索树的下一个节点

    给定一棵二叉搜索树和它的一个节点p,请找出按中序遍历的顺序该节点p的下一个节点。假设二叉搜索树中节点的值都是唯一的。例如,在图8.9的二叉搜索树中,节点8的下一个节点是节点9,节点11的下一个节点是null。 解决这个问题的最直观的思路就是采用二叉树的中序遍历

    2024年02月06日
    浏览(38)
  • 算法刷题Day 22 二叉搜索树的最近公共祖先+二叉搜索树中的插入操作+删除二叉搜索树中的节点

    根据二叉搜索树的性质,相比普通二叉树可以极大程度的简化代码,作为公共祖先其值一定在两个给定节点值之间,从树根往下遍历,第一次出现两个给定节点值之间的值,那个节点即为最近公共祖先(为什么是最近不是最远?根节点一般为最远,第一次出现的值处于两个给

    2024年02月17日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包