}
public TreeNode f(int[] nums,int x,int y){
if(x>y) return null;
TreeNode root=new TreeNode();
int s=(x+y)/2;
root.val=nums[s];
root.left=f(nums,x,s-1);
root.right=f(nums,s+1,y);
return root;
}
}
Q4.3 特定深度节点链表给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
示例：
输入：[1,2,3,4,5,null,7,8]
1
/
2 3
/
4 5 7
/
8
输出：[[1],[2,3],[4,5,7],[8]]
class Solution {
public ListNode[] listOfDepth(TreeNode root) {
if (root == null) {
return null;
}
//BFS中的队列
Queue queue = new linkedList<>();
//先把根节点入队，然后执行“d一个，加n个”
queue.add(root);
//存放每个链表第一个有实际值(非哑元)节点的容器,ArrayList实际上是一个可变长的数组
List list = new ArrayList<>();
//只要队列中还有元素就要不停的出队，直到队列中的所有元素都已出队
while (!queue.isEmpty()) {
//当前队列的长度，即当前层元素的总个数
int size = queue.size();
//链表的头结点，不放实际的值（哑元）
ListNode head = new ListNode(0);
//链表移动指针，让它始终指向当表链表的最后一个元素
ListNode p = head;
//将当前层的节点逐个出队，把出队节点的子节点入队
for (int i = 0; i < size; i++) {
TreeNode poll = queue.poll();
//链表元素追加
p.next = new ListNode(poll.val);
//指针向后移动一个元素，使p指向链表末尾
p = p.next;
if (poll.left != null) {
//当前出队的节点有左孩子，则左孩子入队
queue.add(poll.left);
}
if (poll.right != null) {
//当前出队的节点有右孩子，则右孩子入队
queue.add(poll.right);
}
}
//for循环走完后就遍历完了一层，将存储该层节点的链表第一个有实际值的节点入队
list.add(head.next);
}
//将可变长的数组转化成定长数组（因为函数的返回值要求了返回一个定长数组ListNode[]）
return list.toArray(new ListNode[list.size()]);
}
}
Q4.4 检查平衡性实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/
2 2
/
3 3
/
4 4
返回 false 。
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
int x=depth(root.left);
int y=depth(root.right);
if(x-y>=-1&&x-y<=1){
boolean m=isBalanced(root.left);
boolean n=isBalanced(root.right);
return m&&n;
}else{
return false;
}
}
public int depth(TreeNode root){
if(root==null) return 0;
return Math.max(depth(root.left),depth(root.right))+1;
}
}
Q4.5 合法二叉搜索树实现一个函数，检查一棵二叉树是否为二叉搜索树。
示例 1:
输入:
2
/
1 3
输出: true
示例 2:
输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
二叉搜索树的定义如下
一个节点的左子树上节点的值都小于自身的节点值
一个节点的右子树上节点的值都小于自身的节点值
所有节点的左右子树都必须是二叉搜索树
采用递归中序遍历方法依次比较当前节点值和后一个节点值的大小，若当前节点值大于等于后一个节点值，则不是 二叉搜索树：
class Solution {
Integer pre = null;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (isValidBST(root.left)) {
if (pre == null) pre = root.val;
else {
if (root.val <= pre) return false;
else pre = root.val;
}
return isValidBST(root.right);
}
return false;
}
}
Q4.8 首个共同祖先设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
3
/
5 1
/ /
6 2 0 8
/
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。因为根据定义最近公共祖先节点可以为节点本身。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null)
return null;
if(p == root || q == root)
return root;
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
if(l != null && r != null)
return root;
return l == null ? r : l;
}
}
Q4.9 二叉搜索树序列从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。
示例：
给定如下二叉树
2
/
1 3
返回：
[
[2,1,3],
[2,3,1]
]
分析：
根据题意分析可知，插入元素的顺序必须从根节点开始插入，也就是先插入2后，才可以插入1和3。那么我们维护一个可以访问的节点列表，每轮递归都依次访问列表中的元素，当访问元素有孩子结点时，把孩子结点加入到列表中，然后再去依次访问列表中的元素，当列表为空时，表示产生了一个有效的序列，把它加入到结果集当中。注意访问结点时，要先在列表中删除掉，访问结束后记得恢复。
class Solution {
public List BSTSequences(TreeNode root) {
res = new linkedList<>();
if(root == null){
res.add(new linkedList<>());
return res;
}
linkedList list = new linkedList<>();
linkedList path = new linkedList<>();
path.add(root.val);
getSequences(root, list, path);
学习宝典对我们开发者来说，一定要打好基础，随时准备战斗。不论寒冬是否到来，都要把自己的技术做精做深。虽然目前移动端的招聘量确实变少了，但中高端的职位还是很多的，这说明行业只是变得成熟规范起来了。竞争越激烈，产品质量与留存就变得更加重要，我们进入了技术赋能业务的时代。
不论遇到什么困难，都不应该成为我们放弃的理由！
很多人在刚接触这个行业的时候或者是在遇到瓶颈期的时候，总会遇到一些问题，比如学了一段时间感觉没有方向感，不知道该从那里入手去学习，对此我针对Android程序员，我这边给大家整理了一套学习宝典！包括不限于高级UI、性能优化、移动架构师、NDK、混合式开发（ReactNative+Weex）微信小程序、Flutter等全方面的Android进阶实践技术；希望能帮助到大家，也节省大家在网上搜索资料的时间来学习，也可以分享动态给身边好友一起学习！
【Android核心高级技术PDF文档，BAT大厂面试真题解析】
【算法合集】
【延伸Android必备知识点】
【Android部分高级架构视频学习资源】
定要打好基础，随时准备战斗**。不论寒冬是否到来，都要把自己的技术做精做深。虽然目前移动端的招聘量确实变少了，但中高端的职位还是很多的，这说明行业只是变得成熟规范起来了。竞争越激烈，产品质量与留存就变得更加重要，我们进入了技术赋能业务的时代。
不论遇到什么困难，都不应该成为我们放弃的理由！
很多人在刚接触这个行业的时候或者是在遇到瓶颈期的时候，总会遇到一些问题，比如学了一段时间感觉没有方向感，不知道该从那里入手去学习，对此我针对Android程序员，我这边给大家整理了一套学习宝典！包括不限于高级UI、性能优化、移动架构师、NDK、混合式开发（ReactNative+Weex）微信小程序、Flutter等全方面的Android进阶实践技术；希望能帮助到大家，也节省大家在网上搜索资料的时间来学习，也可以分享动态给身边好友一起学习！
【Android核心高级技术PDF文档，BAT大厂面试真题解析】
[外链图片转存中…(img-lFVli6Us-1643533189613)]
【算法合集】
[外链图片转存中…(img-pK8cew8O-1643533189614)]
【延伸Android必备知识点】
[外链图片转存中…(img-Jq75Dnl7-1643533189615)]
【Android部分高级架构视频学习资源】
本文已被CODING开源项目：《Android学习笔记总结+移动架构视频+大厂面试真题+项目实战源码》收录
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）