剑指offer刷题笔记（四）
面试题26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
输入：A = [1,2,3], B = [3,1]
输出：false
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
/**
* 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) {
boolean result=false;
if(A!=null&&B!=null){
if(A.val==B.val){
result=isSub(A,B);
}
if(!result){
result=isSubStructure(A.left,B)||isSubStructure(A.right,B);
}
}
return result;
}
public boolean isSub(TreeNode A,TreeNode B){
if(B==null){
return true;
}
if(A==null){
return false;
}
if(A.val!=B.val){
return false;
}
return isSub(A.left,B.left)&&isSub(A.right,B.right);
}
}
面试题27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 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 root;
}
if(root.left==null&&root.right==null){
return root;
}
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
if(root.left!=null){
mirrorTree(root.left);
}
if(root.right!=null){
mirrorTree(root.right);
}
return root;
}
}
面试题28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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;
}
TreeNode left=root.left;
TreeNode right=root.right;
return isson(left,right);
}
public boolean isson(TreeNode left,TreeNode right){
if(left==null&&right==null){
return true;
}
if(left==null||right==null){
return false;
}
if(left.val==right.val){
return isson(left.left,right.right)&&isson(left.right,right.left);
}
else{
return false;
}
}
}
面试题29. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 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) {
int s[]={};
int x = matrix.length;
if(x==0){
return s;
}
int y = matrix[0].length;
int[] result = new int[x * y];
int start = 0;
int p = 0;
while (y > start * 2 && x > start * 2) {
int endx = x - start - 1;
int endy = y - start - 1;
for (int i = start; i <= endy; i++) {
result[p] = matrix[start][i];
p++;
}
if (start < endx) {
for (int i = start + 1; i <= endx; i++) {
result[p] = matrix[i][endy];
p++;
}
}
if (start < endx && start < endy) {
for (int i = endy - 1; i >= start; i--) {
result[p] = matrix[endx][i];
p++;
}
}
if (start < endx-1 && start < endy ) {
for (int i = endx - 1; i >= start + 1; i--) {
result[p] = matrix[i][start];
p++;
}
}
start++;
}
return result;
}
}
面试题30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.
class MinStack {
Stack<Integer> s1,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();
*/
面试题31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int poplength=popped.length;
int j=0;
Stack<Integer> stack=new Stack<>();
for(int i=0;i<pushed.length;i++){
stack.push(pushed[i]);
while(!stack.empty()&&j<poplength&&stack.peek()==popped[j]){
stack.pop();
j++;
}
}
return stack.empty();
}
}
面试题32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
/**
* 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) {
int s[]={};
if(root==null){
return s;
}
Queue<TreeNode> queue=new LinkedList<>();
List<Integer> list=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode temp=queue.poll();
list.add(temp.val);
if(temp.left!=null){
queue.offer(temp.left);
}
if(temp.right!=null){
queue.offer(temp.right);
}
}
int[] result=new int[list.size()];
for(int i=0;i<list.size();i++){
result[i]=list.get(i);
}
return result;
}
}
面试题32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
/**
* 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) {
Queue<TreeNode> queue=new LinkedList<>();
List<List<Integer>> result=new ArrayList<>();
if(root==null){
return result;
}
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list=new ArrayList<>();
int size=queue.size();
for(int i=0;i<size;i++) {
TreeNode temp = queue.poll();
list.add(temp.val);
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
result.add(list);
}
return result;
}
}
面试题32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
/**
* 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) {
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
List<List<Integer>> result=new ArrayList<>();
if(root==null){
return result;
}
s1.add(root);
boolean flag=false;
while(!s1.isEmpty()||!s2.isEmpty()){
List<Integer> list=new ArrayList<>();
if(flag){
while(!s2.isEmpty()){
TreeNode node = s2.pop();
list.add(node.val);
if(node.right!=null) s1.add(node.right);
if(node.left!=null) s1.add(node.left);
}
}else{
while(!s1.isEmpty()){
TreeNode node = s1.pop();
list.add(node.val);
if(node.left!=null) s2.add(node.left);
if(node.right!=null) s2.add(node.right);
}
}
result.add(list);
flag=!flag;
}
return result;
}
}
