剑指offer：26-30记录
输入两棵二叉树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
思路：遍历树（前中后都可以，不影响），对每个结点判断是否是子树。
唯一要注意的是定义：
就算图中的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();
-
*/
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/104759174
- 点赞
- 收藏
- 关注作者
评论（0）