#yyds干货盘点# LeetCode刷题集101 - 110

2021年11月24日 阅读数:5
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集101 - 110,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释node

101. 对称二叉树

给定一个二叉树,检查它是不是镜像对称的。数组

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。markdown

    1
   / \
  2   2
 / \ / \
3  4 4  3

可是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:ide

    1
   / \
  2   2
   \   \
   3    3

说明:函数

若是你能够运用递归和迭代两种方法解决这个问题,会很加分。post

PS:
递归的难点在于:找到能够递归的点 为何不少人以为递归一看就会,一写就废。 或者说是本身写没法写出来,关键就是你对递归理解的深不深。ui

对于此题: 递归的点怎么找?从拿到题的第一时间开始,思路以下:this

1.怎么判断一棵树是否是对称二叉树? 答案:若是所给根节点,为空,那么是对称。若是不为空的话,当他的左子树与右子树对称时,他对称code

2.那么怎么知道左子树与右子树对不对称呢?在这我直接叫为左树和右树 答案:若是左树的左孩子与右树的右孩子对称,左树的右孩子与右树的左孩子对称,那么这个左树和右树就对称。排序

仔细读这句话,是否是有点绕?怎么感受有一个功能A我想实现,但我去实现A的时候又要用到A实现后的功能呢?

当你思考到这里的时候,递归点已经出现了: 递归点:我在尝试判断左树与右树对称的条件时,发现其跟两树的孩子的对称状况有关系。

想到这里,你没必要有太多疑问,上手去按思路写代码,函数A(左树,右树)功能是返回是否对称

def 函数A(左树,右树): 左树节点值等于右树节点值 且 函数A(左树的左子树,右树的右子树),函数A(左树的右子树,右树的左子树)均为真 才返回真


class Solution {
     public boolean isSymmetric(TreeNode root) {
          if(root == null) return true;
          return isSymmertric(root.left, root.right);
     }

     private boolean isSymmertric(TreeNode t1,TreeNode t2) {
         if(t1 == null && t2 == null) return true;
         if(t1 == null || t2 == null) return false;
         if(t1.val != t2.val) return false;
         return isSymmertric(t1.left, t2.right) && isSymmertric(t1.right, t2.left);
     }
}

102. 二叉树的层次遍历

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问全部节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

[
[3],
[9,20],
[15,7]
]


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<TreeNode>();
    queue.add(root);
    while(!queue.isEmpty()){
        int count = queue.size();
        List<Integer> list = new ArrayList<Integer>();
        while(count > 0){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null)
                queue.add(node.left);
            if(node.right != null)
                queue.add(node.right);
            count--;
        }
        res.add(list);
    }
    return res;
}
}

103. 二叉树的锯齿形层次遍历

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历以下:

[
[3],
[20,9],
[15,7]
]


class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        traversal(root, res, 0);
        return res;
    }

    private void traversal(TreeNode root, List<List<Integer>> res, int level) {
        if (root == null) {
            return;
        }

        if (res.size() == level) {
            res.add(new ArrayList<Integer>());
        }

        if ((level & 1) == 1){
            res.get(level).add(0, root.val);
        } else {
            res.get(level).add(root.val);
        }

        traversal(root.left, res, level + 1);
        traversal(root.right, res, level + 1);
    }
}

104. 二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。


class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你能够假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回以下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

class Solution {
     private int pre=0;
    private int in=0;
    public TreeNode buildTree(int [] preorder, int [] inorder) {
        return buildTree(preorder,inorder,Integer.MAX_VALUE+1);
    }
    public TreeNode buildTree(int [] preorder,int [] inorder,long stop){
        if(pre==preorder.length){
            return null;
        }
        //走到左下第一个值可返回
        if(inorder[in]==stop){
            in++;
            return null;
        }
        //一直往左下走
        int val=preorder[pre++];
        TreeNode root=new TreeNode(val);

        root.left=buildTree(preorder,inorder,val);
       // 其实往右走,就是返回以前的stop
        root.right=buildTree(preorder,inorder,stop);
        return root;
    }
}

106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你能够假设树中没有重复的元素。

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回以下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode helper(int[] inorder, int[] postorder, int postEnd, int inStart, int inEnd) {
        if (inStart > inEnd) {
            return null;
        }

        int currentVal = postorder[postEnd];
        TreeNode current = new TreeNode(currentVal);

        int inIndex = 0; 
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == currentVal) {
                inIndex = i;
            }
        }
        TreeNode left = helper(inorder, postorder, postEnd - (inEnd- inIndex) - 1, inStart, inIndex - 1);
        TreeNode right = helper(inorder, postorder, postEnd - 1, inIndex + 1, inEnd);
        current.left = left;
        current.right = right;
        return current;
    }
}

107. 二叉树的层次遍历 II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为:

[
[15,7],
[9,20],
[3]
]


class Solution {
     public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if (root == null)
            return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> oneLevel = new ArrayList<>();
            // 每次都取出一层的全部数据
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                oneLevel.add(node.val);
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            // 每次都往队头塞
            result.addFirst(oneLevel);
        }
        return result;
    }
}

108. 将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每一个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它能够表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5

class Solution {
     public TreeNode sortedArrayToBST(int[] nums) {
        // 左右等分创建左右子树,中间节点做为子树根节点,递归该过程
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int l, int r) {
        if (l > r) {
            return null;
        }
        int m = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = buildTree(nums, l, m - 1);
        root.right = buildTree(nums, m + 1, r);
        return root;
    }
}

109. 有序链表转换二叉搜索树

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每一个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它能够表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5

class Solution {
     public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        else if(head.next == null) return new TreeNode(head.val);
        ListNode pre = head;
        ListNode p = pre.next;
        ListNode q = p.next;
        //找到链表的中点p
        while(q!=null && q.next!=null){
            pre = pre.next;
            //p走一倍的速度
            p = pre.next;
            //q走两倍的速度
            q = q.next.next;
        }
        //将中点左边的链表分开
        pre.next = null;
        TreeNode root = new TreeNode(p.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(p.next);
        return root;
    }
}

110. 平衡二叉树

给定一个二叉树,判断它是不是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每一个节点 的左右两个子树的高度差的绝对值不超过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 。

PS:

模版一共三步,就是递归的三部曲:
找终止条件:何时递归到头了?此题天然是root为空的时候,空树固然是平衡的。
思考返回值,每一级递归应该向上返回什么信息?参考我代码中的注释。
单步操做应该怎么写?由于递归就是大量的调用自身的重复操做,所以从宏观上考虑,只用想一想单步怎么写就好了,左树和右树应该当作一个总体,即此时树一共三个节点:root,root.left,root.right。


class Solution {
     //这个ReturnNode是参考我描述的递归套路的第二步:思考返回值是什么
    //一棵树是BST等价于它的左、右俩子树都是BST且俩子树高度差不超过1
    //所以我认为返回值应该包含当前树是不是BST和当前树的高度这两个信息
    private class ReturnNode{
        boolean isB;
        int depth;
        public ReturnNode(int depth, boolean isB){
            this.isB = isB;
            this.depth = depth;
        }
    }
    //主函数
    public boolean isBalanced(TreeNode root) {
        return isBST(root).isB;
    }
    //参考递归套路的第三部:描述单次执行过程是什么样的
    //这里的单次执行过程具体以下:
    //是否终止?->没终止的话,判断是否知足不平衡的三个条件->返回值
    public ReturnNode isBST(TreeNode root){
        if(root == null){
            return new ReturnNode(0, true);
        }
        //不平衡的状况有3种:左树不平衡、右树不平衡、左树和右树差的绝对值大于1
        ReturnNode left = isBST(root.left);
        ReturnNode right = isBST(root.right);
        if(left.isB == false || right.isB == false){
            return new ReturnNode(0, false); 
        }
        if(Math.abs(left.depth - right.depth) > 1){
            return new ReturnNode(0, false);
        }
        //不知足上面3种状况,说明平衡了,树的深度为左右俩子树最大深度+1
        return new ReturnNode(Math.max(left.depth, right.depth) + 1, true);
    }
}