热题HOT 100（41-50）
41.给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
思路
递归结束条件：
都为空指针则返回 true
只有一个为空则返回 false
递归过程：
判断两个指针当前节点值是否相等
判断 A 的右子树与 B 的左子树是否对称
判断 A 的左子树与 B 的右子树是否对称
短路：
在递归判断过程中存在短路现象，也就是做 与 操作时，如果前面的值返回 false 则后面的不再进行计算
时间复杂度：O(n)
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
//秒啊
public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val)
&& isMirror(t1.right, t2.left)
&& isMirror(t1.left, t2.right);
}
42.给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）
利用队列实现二叉树的层次遍历
/**
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null)
return new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int count = queue.size();
List<Integer> list = new ArrayList<>();
while (count>0){
TreeNode temp = queue.poll();
list.add(temp.val);
if(temp.left!=null){
queue.add(temp.left);
}
if(temp.right!=null){
queue.add(temp.right);
}
count--;
}
res.add(list);
}
return res;
}
}
43.给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回它的最大深度 3
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
44.根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
3
/ \
9 20
/ \
15 7
步骤过程:
-
前序数组中最左边的值就是树的头节点值，记为h，并用h生成头节点，记为head，然后在中序数组中找到h，假设位置是i，那么在中序数组中，i左边的数组就是头节点左子树的中序数组，假设长度为l，则左子树的先序数组就是先序数组中h往右长度也为l的数组。
-
用左子树的先序和中序数组，递归整个过程建立左子树，返回的头节点记为left。
-
i右边的数组就是头节点右子树的中序数组，假设长度为r，先序数组中右侧等长的部分就是头节点右子树的先序数组。
-
用右子树的先序和中序数组，递归整个过程建立右子树，返回的头节点记为right。
-
把head的左孩子和右孩子分别设置left和right，返回head，过程结束。
你肯定一脸懵逼
看看例子
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}。
-
首先，根节点 是
{ 1 }；
左子树是：前序{ 2,4,7 }，中序{ 4,7,2 }；
右子树是：前序{ 3,5,6,8 }，中序{ 5,3,8,6 }； -
这时，如果我们把左子树和右子树分别作为新的二叉树(即左子树是：前序
{ 2,4,7 }，中序{ 4,7,2 }看成新的需要重构的二叉树)，一直递归，则可以求出其根节点，左子树和右子树。 -
这样，一直用这个方式，就可以实现重建二叉树。
/*
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
*/
//主功能函数重构二叉树 根据前中序 返回根节点
public TreeNode buildTree(int [] preorder,int [] inorder) {
if(preorder == null || inorder == null||preorder.length==0||inorder.length==0){
return null;
}
TreeNode root = PreAndIn(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
return root;
}
//核心递归
public TreeNode PreAndIn(int[] preorder, int[] inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd) {
TreeNode tree = new TreeNode(preorder[preorderStart]);
if (preorderStart == preorderEnd && inorderStart == inorderEnd) {
return tree;
}
int root = 0;//root表示根节点在中序的位置
//找到前序的第一个元素(即根元素)在中序的位置
for(root= inorderStart; root <= inorderEnd; root++){
if (preorder[preorderStart] == inorder[root]) {
break;
}
}
//左子树的长度
int leftLength = root - inorderStart;
//右子树的长度
int rightLength = inorderEnd - root;
if (leftLength > 0) {
tree.left=(PreAndIn(preorder, inorder, preorderStart+1, preorderStart+leftLength, inorderStart, root-1));
}
if (rightLength > 0) {
tree.right=(PreAndIn(preorder, inorder, preorderStart+1+leftLength, preorderEnd, root+1, inorderEnd));
}
return tree;
}
45.给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
其展开为：
1
\
2
\
3
\
4
\
5
\
6
解法思路
可以发现展开的顺序其实就是二叉树的先序遍历
1.将左子树插入到右子树的地方
2.将原来的右子树接到左子树的最右边节点
3.考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为
null
1
/ \
2 5
/ \ \
3 4 6
//找到1的左子树最右边的节点（就是4），然后把1的右子树接到这个节点的右边
1
/
2
/ \
3 4
1
/
2
/ \
3 4
\
5
\
6
//将 1 的左子树插入到右子树的地方
1
\
2
/ \
3 4
\
5
\
6
//找到2的左子树最右边的节点（就是3），然后把2的右子树接到这个节点的右边
1
\
2
/
3
\
4
\
5
\
6
//将 2 的左子树插入到右子树的地方
1
\
2
\
3
\
4
\
5
\
6
......
代码
public void flatten(TreeNode root) {
while (root != null) {
//左子树为 null，直接考虑下一个节点
if (root.left == null) {
root = root.right;
} else {
// 找左子树最右边的节点
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
//将原来的右子树接到左子树的最右边节点
pre.right = root.right;
// 将左子树插入到右子树的地方
root.right = root.left;
root.left = null;//要记得把左子树置空
// 考虑下一个节点
root = root.right;
}
}
}
46.给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
我们需要找到谷之后的最大的峰
我们可以维持两个变量——
minprice 和 maxprofit，它们分别对应迄今为止所得到的最小的谷值和最大的利润
public int maxProfit(int[] prices) {
int minprice =Integer.MAX_VALUE,maxprofit =0;
for(int i=0;i<prices.length;i++){
if(prices[i]<minprice ){
minprice = prices[i];
}
if(prices[i]-minprice>maxprofit && i>0){//第一天是绝对不会有利润的
maxprofit=prices[i]-minprice;
}
}
return maxprofit;
}
47.给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
二叉树abc，a是根结点（递归中的root），bc是左右子结点（代表其递归后的最优解）。
a
/ \
b c
1.a的父结点+a+b
2.a的父结点+a+c
3.a+b+c
- 情况 1 和 2 ，递归时计算
a + b和a + c，选择一个更优的方案返回，也就是上面说的递归后的最优解。 - 情况 1 ，表示如果不联络父结点的情况，或者它本身是根结点（没有父亲）的情况。这种情况是没法递归的，但是结果有可能是全局最大路径和。
结点有可能是负值，最大和肯定就要想办法舍弃负值（max(0, x)）
private int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root==null)
return 0;
int s = diguiPathSum(root);//返回的是 max(根节点选择左边最优解+本身,根节点选择右边最优解+本身)
// System.out.println(s);
return res;
}
public int diguiPathSum(TreeNode node){
if(node==null)return 0;
int left = diguiPathSum(node.left);
int right = diguiPathSum(node.right);
int fg = node.val+Math.max(0,left)+Math.max(0,right);//不联络a的父亲节点
int dg = node.val+Math.max(0,Math.max(left,right));// 联络a的父亲节点，选择一条路继续递归
res = Math.max(res,Math.max(fg,dg));//存储最大值
return dg;//把a这个节点在联络父亲节点的情况下 传值给上面的父亲
}
48.给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
这道题目最开始想的肯定是
sort，然后计数计算最长序列。但是要求时间复杂度为：o(n)，就不能用sort了。对时间复杂度有要求，就用空间来换，对空间复杂度有要求，就用时间来换。
基于这种思路我们就想要求最长的，就是要记录下有没有相邻的元素，比如遍历到100这个元素，我们需要查看[99, 101]这两个元素在不在序列中，这样去更新最大长度。而记录元素有没有这个事，用set这种数据结构，而set这种数据结构是需要o(n)的空间来换取的，这就是我们刚才说的用空间来换时间
public int longestConsecutive(int[] nums){
Set<Integer> numset = new HashSet<>();
if(nums.length==0)
return 0;
for(int temp : nums){
numset.add(temp);
}
int longres = 0;
for(int temp : nums){
if(numset.remove(temp)){
int left = temp;
int right = temp;
// 向当前元素的左边搜索,eg: 当前为100, 搜索：99，98，97,...
while (numset.remove(left-1))
left--;
// 向当前元素的右边搜索,eg: 当前为100, 搜索：101，102，103,...
while (numset.remove(right+1))
right++;
// 搜索完后更新longres.
longres = Math.max(longres,right-left+1);
}
}
return longres;
}
49.在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
根据时间复杂度我们自然想到二分法，从而联想到归并排序
通过递归实现链表归并排序，有以下两个环节：
1.分割 cut 环节：
找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；
我们使用fast,slow快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
找到中点slow后，执行slow.next = None将链表切断。
递归分割时，输入当前链表左端点head和中心节点slow的下一个节点tmp(因为链表是从slow切断的)。
cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。
2.合并 merge 环节：
将两个排序链表合并，转化为一个排序链表。
双指针法合并，建立辅助ListNode h作为头部。
设置两指针left, right分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
返回辅助ListNode h作为头部的下个节点h.next。
时间复杂度O(l + r)，l,r分别代表两个链表长度。
当题目输入的head == None时，直接返回None。
主要考察3个知识点，
知识点1：归并排序的整体思想
知识点2：找到一个链表的中间节点的方法
知识点3：合并两个已排好序的链表为一个新的有序链表
public ListNode sortList(ListNode head) {//这个head 是4 不是头节点
if(head==null||head.next==null)
return head;
return cutList(head);
}
public ListNode cutList(ListNode head){
if(head.next==null)//递归终止
return head;
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while(fast!=null&&fast.next!=null){//这个条件位置不能变 先判断fast!=null ,再判断fast.next 俩个都是对快指针判断
pre = slow;
slow=slow.next;
fast=fast.next.next;
}
pre.next=null;//统一断开慢指针的前面的连接 让慢指针做下一节链表的头
ListNode l = cutList(head);
ListNode r = cutList(slow);
return merge(l,r);
}
public ListNode merge(ListNode l ,ListNode r){
ListNode head2 = new ListNode(0);//保留头节点
ListNode cur = head2;
while(l!=null&&r!=null){
if(l.val<r.val){
cur.next=l;
l=l.next;
}else{
cur.next=r;
r=r.next;
}
cur=cur.next;
}
cur.next=(l!=null)?l:r;
return head2.next;
}
50.给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE, imax = 1, imin = 1; //一个保存最大的，一个保存最小的。
for(int i=0; i<nums.length; i++){
if(nums[i] < 0){ int tmp = imax; imax = imin; imin = tmp;} //如果数组的数是负数，那么会导致最大的变最小的，最小的变最大的。因此交换两个的值。
imax = Math.max(imax*nums[i], nums[i]);
imin = Math.min(imin*nums[i], nums[i]);
max = Math.max(max, imax);
}
return max;
}
