数据结构java版之二叉树（部分offer面试题篇），2024年最新项目总面试题目
先自我介绍一下，小编浙江大学毕业，去过华为、字节跳动等大厂，目前阿里P7
深知大多数程序员，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！
因此收集整理了一份《2024年最新Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友。
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上Java开发知识点，真正体系化！
由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新
如果你需要这些资料，可以添加V获取：vip1024b （备注Java）
正文
int count=0;
//以遍历的思路写
int size1(BTNode root){
if(root==null) {
return 0;
}else{
count++;
size1(root.left);
size1(root.right);
}
return count;
}
②子问题思路：
代码如下：
//以子问题思路写
int size(BTNode root){
if(root==null){
return 0;
}
return size(root.left)+size(root.right)+1;
}
2.获取叶子节点的个数
两种思考方式：
①遍历实现：
代码：
//以遍历的方式访问
int count1=0;
int getLeafNodeCount(BTNode root){
// int count1=0;
if(root==null){
return 0;
}else if(root.left==null && root.right==null){
count1++;
}
getLeafNodeCount(root.left);
getLeafNodeCount(root.right);
return count1;
}
②子问题思路：
代码如下：
int getLeafNodeCount(BTNode root){
if(root==null){
return 0;
}else if(root.left==null && root.right==null){
return 1;
}
return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
}
}
3.子问题思路-求叶子结点个数
该题在2中第二个思路中已经求得
4.获取第K层节点的个数
解题思路：
代码如下：
//求第K层结点的个数
public int getKLevelNodeCount(int k){
return getKLevelNodeCount(root, k);
}
// 获取第K层结点的个数
private int getKLevelNodeCount(BTNode root,int k){
if(root==null || k<=0){
return 0;
}
if(k==1){
return 1;
}
return getKLevelNodeCount(root.left, k-1)+getKLevelNodeCount(root.right, k-1);
}
5.获取二叉树的高度
思路分析：
代码如下：
// 获取二叉树的高度（时间复杂度为O（n））
int getHeight(BTNode root){
if(root==null){
return 0;
}
int leftHeight=getHeight(root.left);
int rightHeight=getHeight(root.right);
//此处用的是三目运算符求取两者中的较大值
return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
}
6.检测值为value的元素是否存在
解题思路：
代码如下 ：
// 检测值为value的元素是否存在
boolean find(BTNode root, int val) {
if (root == null) {
return false;
} else if (root.val == val) {
return true;
}
if (find(root.left, val) || find(root.right, val)) {
return true;
}
return false;
}
7.判断一棵树是不是完全二叉树
解题思路：
代码如下：
boolean isCompleteTree(BTNode root){
if(root == null) return true;
Queue<BTNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
BTNode cur = queue.poll();
if(cur != null) {
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
//第二个while循环实质上就是在cur=null的基础上来判断实现的，若是整个为空即null 则true；反之为false
while (!queue.isEmpty()) {
BTNode top = queue.peek();
if(top != null) {
return false;
}
queue.poll();
}
return true;
}
1. 检查两颗树是否相同
100. 相同的树 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/same-tree/
解题思路：
要判断两棵树是否相同：
①数的结构相同
②相应位置的结点对应的数值相同
代码如下：
public boolean isSameTree(TreeNode p, TreeNode q ){
if(p == null && q != null || p != null && q == null) {
return false;
}
if(p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
//p != null && q!= null && p.val == q.val
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
2. 另一颗树的子树
代码如下：
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null || subRoot == null) {
return false;
}
//根节点和subroot是不是两颗相同的树
if(isSameTree(root,subRoot)) {
return true;
}
//subRoot是不是root的左子树
if(isSubtree(root.left,subRoot)) {
return true;
}
if(isSubtree(root.right,subRoot)) {
return true;
}
return false;
}
}
3. 二叉树最大深度
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/同二叉树基本操作的5题，请参考此篇博客上方
4. 判断一颗二叉树是否是平衡二叉树
https://leetcode-cn.com/problems/balanced-binary-tree/submissions/解题思路：
class Solution {
public int height (TreeNode root) {
if(root == null) {return 0;}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return (leftHeight > rightHeight) ?
(leftHeight+1) :(rightHeight+1);
}
/**
时间复杂度：O(N^2)
*/
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int left = height(root.left);
int right = height(root.right);
return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
5. 对称二叉树
101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/symmetric-tree/解题思路：
代码如下：
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isSymmetricChild(root.left,root.right);
}
public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
//第一种情况
if(leftTree == null && rightTree == null) return true;
//第二种情况
if((leftTree == null && rightTree != null)||(leftTree != null && rightTree == null)) return false;
//第三种情况
if(leftTree.val != rightTree.val) return false;
return isSymmetricChild(leftTree.left,rightTree.right) &&
isSymmetricChild(leftTree.right,rightTree.left);
}
6. 二叉树的构建及遍历牛客网链接
http:///www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
7. 二叉树的分层遍历
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/解题思路：
借助一个队列和一个临时变量cur来打印分层遍历
①讨论根是否为空的情况
②当队列不为空时，出队列中的队尾元素到cur中，并通过cur.val进行打印
③循环讨论子左右子树的情况，所以要用while进行循环
两类代码：
①普通代码：
//打印层序遍历二叉树
public void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
//①判断树是否为空的情况
if(root == null) return;
queue.offer(root);
//②判断队列是否为空
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val+" ");
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}
}
②OJ上解题的代码：
解题思路：
代码如下：
//层序遍历访问打印元素
List<List> ret = new ArrayList<>();
if(root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
//当前的结点个数size
int size = queue.size();
List<Integer> list = new ArrayList<>();
while (size != 0) {
TreeNode cur = queue.poll();
//将同层结点放在一个list中
list.add(cur.val);
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
size--;//1 0
}
//将所有一层link的结点放在同一个list中
ret.add(list);
}
//最后返回整个所需的ret
return ret;
}
8. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/解题思路：
思路①：由二叉搜索树的思想来设计二叉树的方法
若是二叉搜索树
详细思路：
1.rootp || rootq(p,q为结点）
此时的最近公共祖先是root
2.可能均在根的左边或者右边
①p.val<root.val && q.val<root.val(p,q均在root的左子树中）
最近公共祖先在左子树中
②p.val>root.val && q.val>root.val(p,q均在root的右子树中）
最近公共祖先在右子树中
3.最近的公共祖先就是root
①p.val>root.val && q.val<root.val(p在左子树中，q在右子树中）
②p.val<root.val && q.val>root.val(p在右子树中，q在左子树中）
代码如下：
//二叉树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}if(root==p||root==q){
return root;
}
TreeNode l=lowestCommonAncestor(root.left,p,q);
TreeNode r=lowestCommonAncestor(root.right,p,q);
if(l!=null && r!=null){
return root;
}else if(l!=null){
return l;
}else{
return r;
}
}
}
思路②：
由孩子双亲表示法来求取
代码如下：
class Solution {
//root:
public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode>stack){
if(rootnull || nodenull){
return false;
}stack.push(root);
if(root==node){
return true;
}
boolean flg=getPath(root.left,node,stack);
if(flg==true){
return true;
}
flg=getPath(root.right,node,stack);
if(flg==true){
return true;
}
stack.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
Stack<TreeNode> stack1=new Stack<>();
getPath(root,p,stack1);
Stack<TreeNode> stack2=new Stack<>();
getPath(root,q,stack2);
int size1=stack1.size();
int size2=stack2.size();
if(size1>size2){
int size=size1-size2;
while(size!=0){
stack1.pop();
size--;
}
while(!stack1.isEmpty() && !stack2.isEmpty()){
//用等号判断地址
if(stack1.peek()==stack2.peek()){
return stack1.pop();
}else{
stack1.pop();
stack2.pop();
}
}
}else{
int size=size2-size1;
while(size!=0){
stack2.pop();
总结
总的来说，面试是有套路的，一面基础，二面架构，三面个人。
最后，小编这里收集整理了一些资料，其中包括面试题（含答案）、书籍、视频等。希望也能帮助想进大厂的朋友
网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。
需要这份系统化的资料的朋友，可以添加V获取：vip1024b （备注Java）
一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
while(size!=0){
stack1.pop();
size--;
}
while(!stack1.isEmpty() && !stack2.isEmpty()){
//用等号判断地址
if(stack1.peek()==stack2.peek()){
return stack1.pop();
}else{
stack1.pop();
stack2.pop();
}
}
}else{
int size=size2-size1;
while(size!=0){
stack2.pop();
总结
总的来说，面试是有套路的，一面基础，二面架构，三面个人。
最后，小编这里收集整理了一些资料，其中包括面试题（含答案）、书籍、视频等。希望也能帮助想进大厂的朋友
[外链图片转存中…(img-G7x8bAmO-1713135264027)]
[外链图片转存中…(img-YrrMFuJC-1713135264027)]
网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。
需要这份系统化的资料的朋友，可以添加V获取：vip1024b （备注Java）
[外链图片转存中…(img-KlgXTu3e-1713135264028)]
一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
更多推荐
11
0- 0
已为社区贡献1条内容
所有评论(0)