程序员面试金典:二叉树平衡检查、有向路径检查

2023-12-19 21:58

本文主要是介绍程序员面试金典:二叉树平衡检查、有向路径检查,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.二叉树平衡检查

题目描述

实现一个函数,检查二叉树是否平衡,平衡的定义如下,对于树中的任意一个结点,其两颗子树的高度差不超过1。

给定指向树根结点的指针TreeNode* root,请返回一个bool,代表这棵树是否平衡。

import java.util.*;/*
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}*/
public class Balance {public boolean isBalance(TreeNode root) {if(root==null)	return true;int lf=getHigh(root.left);int lr=getHigh(root.right);if(Math.abs(lf-lr)<=1){return isBalance(root.left)&&isBalance(root.right);}else{return false;}}public int getHigh(TreeNode r){if(r==null)	return 0;int left=getHigh(r.left);int right=getHigh(r.right);return left>right?left+1:right+1;}
}

2.有向路径检查

题目描述

对于一个有向图,请实现一个算法,找出两点之间是否存在一条路径。

给定图中的两个结点的指针UndirectedGraphNode* a,UndirectedGraphNode* b(请不要在意数据类型,图是有向图),请返回一个bool,代表两点之间是否存在一条路径(a到b或b到a)。

方法1:用集合

本题涉及到一个深度优先遍历的问题,用HashSet作为是否访问到的某个一个标志,然后将该结点的临界点加入递归参数入口进行递归(用ArrayList或者其他集合也能达到类似效果)

import java.util.ArrayList;
import java.util.HashSet;public class Main {public class UndirectedGraphNode {int label = 0;UndirectedGraphNode left = null;UndirectedGraphNode right = null;ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>();public UndirectedGraphNode(int label) {this.label = label;}}public class Path {public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {if (null == a || null == b)return false;return  checkPathCore(a, b,new HashSet<UndirectedGraphNode>())||checkPathCore(b, a,new HashSet<UndirectedGraphNode>());}public boolean checkPathCore(UndirectedGraphNode a, UndirectedGraphNode b,HashSet<UndirectedGraphNode> map) {if (a == b)return true;map.add(a);// 标记a已被访问for (int i = 0; i < a.neighbors.size(); i++) {if(!map.contains(a.neighbors.get(i))&&checkPathCore(a.neighbors.get(i), b,map))return true;// 发现满足条件的路径立即返回,避免不必要的循环,导致超时。}return false;}}
}
方法2:递归(参考牛客网阿狸不是猫解答)

public class Path {public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {if (a == null || b == null)return false;return check(a, b) || check(b, a);}public boolean check(UndirectedGraphNode a, UndirectedGraphNode b) {if (a == b)return true;//不让其重复遍历if (a.label == -1)return false;a.label = -1;for (int i = 0; i < a.neighbors.size(); i++) {if (check(a.neighbors.get(i), b))return true;}return false;}}
方法3:队列的非递归形式
import java.util.*;/*
public class UndirectedGraphNode {int label = 0;UndirectedGraphNode left = null;UndirectedGraphNode right = null;ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>();public UndirectedGraphNode(int label) {this.label = label;}
}*/
public class Path {HashMap<UndirectedGraphNode,Boolean> map=new HashMap<UndirectedGraphNode,Boolean>();public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {if (a == null || b == null)return false;return check(a, b) || check(b, a);}private boolean check(UndirectedGraphNode a, UndirectedGraphNode b) {if(a==b)	return true;UndirectedGraphNode p=null;Queue<UndirectedGraphNode> queue=new LinkedList<UndirectedGraphNode>();queue.offer(a);map.put(p,true);while(!queue.isEmpty()){p=queue.poll();for (int i = 0; i <p.neighbors.size(); i++) {if(p.neighbors.get(i)==b)	return true;if(!map.containsKey(p.neighbors.get(i))){map.put(p.neighbors.get(i),true);queue.offer(p.neighbors.get(i));}}}return false;}
}


这篇关于程序员面试金典:二叉树平衡检查、有向路径检查的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/513844

相关文章

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1:定义时间段类步骤2:添加时间段步骤3:检查时间段是否有重合步骤4:输出结果示例代码结语作

shell脚本快速检查192.168.1网段ip是否在用的方法

《shell脚本快速检查192.168.1网段ip是否在用的方法》该Shell脚本通过并发ping命令检查192.168.1网段中哪些IP地址正在使用,脚本定义了网络段、超时时间和并行扫描数量,并使用... 目录脚本:检查 192.168.1 网段 IP 是否在用脚本说明使用方法示例输出优化建议总结检查 1

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

使用Python检查CPU型号并弹出警告信息

《使用Python检查CPU型号并弹出警告信息》本教程将指导你如何编写一个Python程序,该程序能够在启动时检查计算机的CPU型号,如果检测到CPU型号包含“I3”,则会弹出一个警告窗口,感兴趣的小... 目录教程目标方法一所需库步骤一:安装所需库步骤二:编写python程序步骤三:运行程序注意事项方法二

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费