热题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;
}

文章参考
https://leetcode-cn.com/problemset/hot-100/