26~36

26. 树的子结构

难度中等603

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构，即 A中有出现和B相同的结构和节点值。

image-20220801202035503

isSubStructure(A, B) ,

有三种情况

以A为根节点的子树包含B (A, B 子结构部分以A开始 => A是根节点) isSame()方法

B是A的左子树的子结构重新isSubStructure(A.left,B)

B是A的右子树的子结构重新isSubStructure(A.right,B)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && 
        (isSame(A, B)|| isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    public boolean isSame(TreeNode A,TreeNode B) { 
        // 等于也不能返回true , 还有子节点,因此要返回 子判断节点是否相同的表达式
        if (B == null) return true;
        if (A == null||A.val!=B.val) return false;
        return isSame(A.left,B.left)&&isSame(A.right,B.right);
    }
}

27. 二叉树的镜像

难度简单287

请完成一个函数，输入一个二叉树，该函数输出它的镜像

递归交换每个节点的左右孩子即可

递归停止条件为: 当传入的节点是叶子结点, return

image-20220801203954127

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        swapTreeNode(root);
        return root;
    }
    public void swapTreeNode(TreeNode root){
        if(root==null) return ; // 传入的节点为null ,说明是叶子结点 ,返回即可
        TreeNode temp =root.left;
        root.left=root.right;
        root.right=temp;
        swapTreeNode(root.left);
        swapTreeNode(root.right);
    }
}

28. 对称的二叉树

难度简单368

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

按照对称的方式遍历左右子树，比较同时遍历的节点是否一致。

采用递归
left.val==right.val 两节点的值相等, 返回true
两节点都为空 ,仍然对称, 返回true

两节点中有一个节点为null ,返回false

Picture1.png

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return f(root.left,root.right);
    }
    public boolean symmetric(TreeNode left,TreeNode right){
        if(left==null&&right==null) return true;
        if(left==null||right==null||left.val!=right.val) return false;
        return f(left.left,right.right) &&f(left.right,right.left);
    }
}

29. 顺时针打印矩阵

难度简单437

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

image-20220801212936835

定义 top right bottom left , 循环,遍历即可

每次循环 top ++ bottom-- left ++ right--

截止条件 bottom<top top>bottom left>right right <left

每次走完一行或者一列都判断是否截止,因为随着矩阵的规模不同,最后遍历的一行的方向可以是思聪方向中的任意一个

因此每次添加完一行 or 一列都需要判断矩阵是否已经添加完毕

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        // 每次循环  top ++  bottom--  l ++  r--
        // 截止条件  bottom<top  top>bottom
        if(matrix.length == 0) return new int[0];
        int left = 0, right = matrix[0].length - 1, top = 0, bottom = matrix.length - 1, idx= 0;
        int[] res = new int[(right + 1) * (bottom + 1)];
        while(true) { // 每次循环 遍历一圈
// 每次走完一行或者一列都判断是否截止,因为随着矩阵的规模不同,最后遍历的一行的方向可以是思聪方向中的任意一个
            for (int i = left; i <=right ; i++) // left to right
                res[idx++] =matrix[top][i];
            if(++top>bottom) break;

            for (int i = top; i <=bottom ; i++)  // top to bottom
                res[idx++] =matrix[i][right];
            if(--right<left) break;

            for (int i = right; i >=left ; i--) // right to left
                res[idx++] =matrix[bottom][i];
            if(--bottom<top) break;

            for (int i = bottom ; i >=top ; i--)  // bottom to top
                res[idx++] =matrix[i][left];
            if(++left>right) break;
        }
        return res;
    }
}

30. 包含min函数的栈

难度简单370

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

java中的list为空（size==0）与list为null的区别

就像空杯子与没有杯子的区别
注意LinkedList实现的是Queue接口

使用Stack 类, 添加min max,

public class MinStack {
    /** initialize your data structure here. */
    Integer min=null;
    Integer max=null;
    Stack<Integer> list=new Stack<>();
    public MinStack() {

    }
    public void push(int x) {
        if(min==null) min=x;
        if(max==null) max=x;
        if(min>x) min=x;
        if(max<x) max=x;
        list.add(x);
    }
    public void pop() {
        int x=list.pop();
        if(list.size()==0){
            min=null;
            return;
        }
        if(x==min){  // 取末尾的元素, 然后遍历list 如果有小于的元素, 再赋值
            min=list.get(0);
            for(Integer a:list){
                if(a<=min)
                    min=a;
            }
        }
    }

    public int top() {
        return  list.get(list.size()-1);
    }
    public int min() {
        return min;
    }

}

31. 栈的压入、弹出序列

难度中等363

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

使用一个stack来通过题目给的序列来模拟出栈和入栈操作,

如果模拟成功, 那么最后这个stack应该是空的 , 返回栈是否为空即可

入栈操作：按照压栈序列的顺序执行。

出栈操作：每次入栈后，循环判断 “栈顶元素 == 弹出序列的当前元素” 是否成立

将符合弹出序列顺序的栈顶元素全部弹出。

由于题目的元素不重复 , 因此遇到元素相同的情况即可出栈

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack=new Stack<>();
        int i=0;
        for (int num:pushed) {
            stack.push(num);
            while(stack.size()!=0 && stack.peek()==popped[i]){
                // 如果在添加的过程中 , 将要添加的元素== 当前 popped对象下标的元素, 那么就弹出当前 添加的元素,
                // 如果 popped为true, 那么能 完全弹出, 如果不是出栈的序列, 那么最终stack 内一定会有没有出栈的 元素
                i++;
                stack.pop();
            }
        }
        return  stack.size()==0;
    }
}

32 - I. 从上到下打印二叉树I

难度中等224

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。

BFS 通常借助队列的先入先出特性来实现。

利用队列的特性 , 将right 的顺序排在了 left 的孩子的前面 , 从而实现从左至右添加

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null) return new int[0];
        LinkedList<TreeNode> queue=new LinkedList<>();
        List<Integer> list=new ArrayList<>();
        queue.add(root);
        while(queue.size()!=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);
        }
        int []res=new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i]=list.get(i);
        }
        return res;
    }
}

32 - II. 从上到下打印二叉树 II

难度简单241

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

image-20220803144136843

这个题的关键点是在上一题的基础上 , 在while循环内一次就清空上一次添加的节点, 然后再让这些节点的子节点入队

/**
 * Definition for a binary tree node.
 * 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.size()!=0){
            List<Integer> list=new ArrayList<>();
            for (int i = queue.size(); i >0 ; i--) {
                // 通过使用循环 ,每次都清空上一次while循环入队的节点. 同时也会添加这些节点的孩子
                TreeNode temp = queue.poll();
                list.add(temp.val);
                // 添加左右节点
                if(temp.left!=null)
                    queue.add(temp.left);
                if(temp.right!=null)
                    queue.add(temp.right);
            }
            res.add(list);
        }
        return res;
    }
}

32 - III. 从上到下打印二叉树 III

难度中等241

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

     3
   /   \
  9     20
 / \   /  \
4  	6  12  8

就是按照蛇形打印二叉树

不同于原本的使用的队列, 这里使用的是stack

使用stack先进后出的特性,

如果这一行的顺序是从左到右(以第1行为例) , 由于下一行输出的时候应该是先添加 20 的val ,然后再添加 9.val 因此要把20 放在栈顶, 所以在添加的时候从左到右 应该先添加 left 再添加right

对于从右到左, 以第2行为例, 那么第三行的顺序就该是从左到右 , 会先添加4.val 所以要最后添加 4 节点 , 因此所以在添加的时候从右到左 应该先添加 right 再添加left

/**
 * Definition for a binary tree node.
 * 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<>();
        Stack<TreeNode> stack=new Stack<>();
        stack.add(root);
        int cnt=0;
        while(stack.size()!=0){
            List<Integer> list=new ArrayList<>();
            List<TreeNode> treeNodeList=new ArrayList<>();
            while(stack.size()!=0){   // 将上一轮循环存入的节点 都出栈 ,treeNodeList
                treeNodeList.add(stack.pop());
            }
            if(cnt==0){
                //从左往右
                for (TreeNode temp: treeNodeList) {
                    list.add(temp.val);
                    if(temp.left!=null)
                        stack.add(temp.left);
                    if(temp.right!=null)
                        stack.add(temp.right);
                }
                cnt++;
            }else{
                // 从右往左
                for (TreeNode temp: treeNodeList) {
                    list.add(temp.val);
                    if(temp.right!=null)
                        stack.add(temp.right);
                    if(temp.left!=null)
                        stack.add(temp.left);
                }
                cnt--;
            }
            res.add(list);
        }
        return res;
    }
}

33. 二叉搜索树的后序遍历序列

难度中等573

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

后序遍历 :

左右根

二叉搜索树:

左子树中所有节点的值< 根节点的值；右子树中所有节点的值 > 根节点的值；

其左、右子树也分别为二叉搜索树。

通过递归，判断所有子树的 正确性 （即其后序遍历是否满足二叉搜索树的定义），若所有子树都正确，则此序列为二叉搜索树的后序遍历。

k==j 说明当前的这个树是正确的
- 如果k!=j

postorder[i] ~ postorder[j] 表示的是当前树的区间

k=0 , 由于本题是后序遍历, 0~i 的所有端点都会满足 <postorder[j], 因此即使是写成了k=0, 也不会错,不过会导致循环的次数多,耗费时间

class Solution {
    public boolean verifyPostorder(int[] postorder) { 
        return isRight(postorder, 0,postorder.length-1);
    }
    public boolean isRight(int []postorder,int i,int j){ //i, j  表示这个树的 左右端点
        if(i>j) return true; // 说明这个位置没有节点 ,直接返回true
        int k=i; // 直接从当前树的最左端的端点开始
// k=0 , 由于本题是后序遍历, 0~i 的所有端点都会满足 <postorder[j], 因此即使是写成了k=0, 也不会错,不过会导致循环的次数多,耗费时间
        while(postorder[k]<postorder[j]){
            k++;
        }
        int r=k; //这个是右子树的开始的位置
        while(postorder[k]>postorder[j]) {
            k++;
        }
        return k==j&&isRight(postorder,i,r-1)&&isRight(postorder,r,j-1);  
        //左右子树的后续遍历不能取到 端点,所以需要 -1
    }
}

34. 二叉树中和为某一值的路径

一篇文章解决所有二叉树路径问题（问题分析+分类模板+题目剖析） - 求和路径 - 力扣（LeetCode）

难度中等361

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

image-20220803155254603

当心static!

class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>(); 
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        recur(root, sum);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

112. 路径总和

难度简单967

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

class Solution {
    int ans=0;
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root==null) return false;
        dfs(root,sum);
        return ans!=0;
    }
    public void dfs(TreeNode root, int target){
        if(root==null) return ;
        if(root.val==target&&root.left==null&root.right==null){ 
            // 验证是否是叶子结点, 直接 root.left==null&root.right==null
            ans++;
            return ;
        }
        dfs(root.left,target-root.val);
        dfs(root.right,target-root.val);
    }
}

35. 复杂链表的复制

难度中等570

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

利用hashmap , key value 的类型均是 Node , 使用两次循环, 第一次先将 Node 以 new 的形式存储到map 里面

第二次循环 : 通过hashmap的特性, 将 random以及next 依次赋值 ,

最终返回 map.get(head);

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        Node now=head;
        Map<Node,Node> map=new HashMap<>();
        Node pre=null;
        while(now!=null){ // 先把链表复制到 map里面 ,  建立 “原节点 -> 新节点” 的 Map 映射
            map.put(now,new Node(now.val));
            now=now.next;
        }
        now=head;
        while(now!=null){
            map.get(now).random=map.get(now.random);
            map.get(now).next=map.get(now.next);
            now=now.next;
        }
        return map.get(head);
    }
}

36. 二叉搜索树与双向链表

难度中等552

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

image-20220804150901036image-20220804150929209

使用中序遍历(左根右), 从大到小访问所有节点

并在访问每个节点时构建 cur 和前驱节点 pre 的引用指向；

cur表示当前的节点

pre表示当前节点的前面的那个节点

中序遍历结束后, 最后的now刚好是 5 , 由于pre=now, 此时的pre也是指向这个节点, 也就是尾结点

遍历完成返回treeToDoublyList后，最后构建头节点和尾节点的引用指向即可。

pre为空 , 说明这个节点是头结点 ,

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
 Node pre=null,head=null; // 分别代表 当前节点的前面的那个节点 以及头结点   , 遍历结束后, pre 的指向是尾结点
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        dfs(root); // 中序遍历构造链表
        // 链接首尾节点
        pre.right=head;
        head.left=pre;
        return head;
    }

    void dfs(Node now){ // 中序遍历
        if(now==null) return ;
        dfs(now.left);
        if(pre==null) head=now; // pre为空 ,说明当前的节点为头结点
        else pre.right=now;
        now.left=pre;
        pre=now;// 当前节点右移
        dfs(now.right);
    }
}