剑指offer：26-30记录

川长思鸟来 2023-07-13 03:10 2阅读 0赞

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

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

例如:  
给定的树 A:

3  
/ \\  
4 5  
/ \\  
1 2  
给定的树 B：

4  
/  
1  
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = \[1,2,3\], B = \[3,1\]  
输出：false  
示例 2：

输入：A = \[3,4,5,1,2\], B = \[4,1\]  
输出：true

思路：遍历树（前中后都可以，不影响），对每个结点判断是否是子树。

唯一要注意的是定义：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

就算图中的1还有左右孩子，依旧算匹配成功。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    /**
     * 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) {
         if(A == null || B == null){
            return false;
         }
        return issub(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
        }
    
        //判断是否是子树
        public boolean issub(TreeNode A, TreeNode B){
            if(B == null){
                return true;
            }
            if(A == null && B != null){
                return false;
            }
            if(A.val == B.val){
                return issub(A.left,B.left) && issub(A.right,B.right);
            }
            return false;
        }
    }

--------------------

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

例如输入：

4  
/ \\  
2 7  
/ \\ / \\  
1 3 6 9  
镜像输出：

4  
/ \\  
7 2  
/ \\ / \\  
9 6 3 1

示例 1：

输入：root = \[4,2,7,1,3,6,9\]  
输出：\[4,7,2,9,6,3,1\]

思路，找递归定义。

/**
     * 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) {
            if(root==null){
                return null;
            }
            TreeNode temp=root.left;
            root.left=root.right;
            root.right=temp;
            mirrorTree(root.left);
            mirrorTree(root.right);
            return root;
        }
    }

--------------------

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

例如，二叉树 \[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

示例 1：

输入：root = \[1,2,2,3,4,4,3\]  
输出：true  
示例 2：

输入：root = \[1,2,2,null,3,null,3\]  
输出：false

思路：递归判断

/**
     * 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 help(root.left,root.right);
        }
        public boolean help(TreeNode node1,TreeNode node2){
            if(node1==null && node2==null){
                return true;
            }
            if(node1==null || node2==null){
                return false;
            }
            return node1.val==node2.val && help(node1.left,node2.right) && help(node1.right,node2.left);
        }
    }

--------------------

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

示例 1：

输入：matrix = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\]  
输出：\[1,2,3,6,9,8,7,4,5\]  
示例 2：

输入：matrix = \[\[1,2,3,4\],\[5,6,7,8\],\[9,10,11,12\]\]  
输出：\[1,2,3,4,8,12,11,10,9,5,6,7\]

限制：

0 <= matrix.length <= 100  
0 <= matrix\[i\].length <= 100

思路：一圈一圈往里打印。顺时针

class Solution {
        public int[] spiralOrder(int[][] matrix) {
            if(matrix == null || matrix.length == 0)
        		return new int[0];
            int m = matrix.length;
            int n = matrix[0].length;
            int[] ans=new int[m*n];
            int ansIndex=0;
            int i = 0; 
    
            //统计矩阵从外向内的层数，如果矩阵非空，那么它的层数至少为1层
            int count = (Math.min(m, n)+1)/2;
            //从外部向内部遍历，逐层打印数据
            while(i < count) {
            	for (int j = i; j < n-i; j++)ans[ansIndex++]=matrix[i][j];//向右的那一行
            	for (int j = i+1; j < m-i; j++)ans[ansIndex++]=matrix[j][(n-1)-i];//向下的那一列
            	for (int j = (n-1)-(i+1); j >= i && (m-1-i != i); j--)ans[ansIndex++]=matrix[(m-1)-i][j];//向左的那一行
            	for (int j = (m-1)-(i+1); j >= i+1 && (n-1-i) != i; j--)ans[ansIndex++]=matrix[j][i];//向上的那一列
            	i++;
            }    
            return ans;
        }
    }

--------------------

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

示例:

MinStack minStack = new MinStack();  
minStack.push(-2);  
minStack.push(0);  
minStack.push(-3);  
minStack.min(); --> 返回 -3.  
minStack.pop();  
minStack.top(); --> 返回 0.  
minStack.min(); --> 返回 -2.

提示：

各函数的调用总次数不超过 20000 次

思路：拿另外一个栈同步记录当前最即可。

class MinStack {
        private Stack<Integer> s1;
        private Stack<Integer> s2;
        /** initialize your data structure here. */
        public MinStack() {
            s1=new Stack<>();
            s2=new Stack<>();
        }
        
        public void push(int x) {
            s1.add(x);
            if(s2.empty()||s2.peek()>x)s2.add(x);
            else s2.add(s2.peek());
        }
        
        public void pop() {
            s1.pop();
            s2.pop();
        }
        
        public int top() {
            return s1.peek();
        }
        
        public int min() {
            return s2.peek();
        }
    }
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.min();
     */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309191218687.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70