- 01. 数组中重复的数字
- 02. 二维数组中的查找
- 03. 替换空格
- 04. 从尾到头打印链表
- 05. 重建二叉树
- 06. 用两个栈实现队列
- 07. 斐波那契数列
- 08. 青蛙跳台阶问题
- 09. 旋转数组的最小数字
- 10. 矩阵中的路径
- 11. 机器人的运动范围
- 12. 剪绳子<动态规划>
- 13. 剪绳子<贪心算法，大数取余>
- 14. 二进制中1的个数
- 15. 数值的整数次方
- 16. 打印从1到最大的n位数（大数问题）
- 17. 删除链表的节点
- 18. 正则表达式匹配（Hard）
- 19. 表示数值的字符串
- 20. 调整数组顺序使奇数位于偶数前面
- 21. 链表中倒数第k个节点
- 22. 反转链表
- 23. 合并两个排序的链表
- 24. 树的子结构
- 25. 二叉树的镜像
01. 数组中重复的数字
class Solution {
public int findRepeatNumber(int[] nums) {
for(int i = 0;i < nums.length; i++){
while(nums[i] != i){
if(nums[i] == nums[nums[i]]){
return nums[i];
} else {
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
}
return -1;
}
}
02. 二维数组中的查找
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix.length == 0){
return false;
}
int row = 0;
int col = matrix[0].length-1;
while(row < matrix.length && col >= 0){
if(target == matrix[row][col]){
return true;
} else if(target > matrix[row][col]) {
row ++;
} else if(target < matrix[row][col]) {
col --;
}
}
return false;
}
}
03. 替换空格
// class Solution {
// public String replaceSpace(String s) {
// return s.replaceAll(" ","%20");
// }
// }
class Solution{
public String replaceSpace(String s) {
if(s == null){
return null;
}
int cnt = 0;
for(int i = 0;i < s.length();i++){
if(s.charAt(i) == ' '){
cnt ++;
}
}
cnt = s.length() + cnt * 2;
char[] s_char = new char[cnt];
int p1 = s.length()-1;
int p2 = cnt-1;
while(p1>=0 && p2>=0){
if(s.charAt(p1) != ' '){
s_char[p2] = s.charAt(p1);
p2 --;
p1 --;
} else{
s_char[p2] = '0';
p2 --;
s_char[p2] = '2';
p2 --;
s_char[p2] = '%';
p2 --;
p1 --;
}
}
return new String(s_char);
}
}
04. 从尾到头打印链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
//用栈的方法
class Solution {
public int[] reversePrint(ListNode head) {
if(head == null){
return new int[]{};
}
ListNode temp = head;
Stack<ListNode> stack = new Stack<ListNode>();
while(temp != null){
stack.push(temp);
temp = temp.next;
}
int size = stack.size();
int[] vec = new int[size];
for(int i = 0;i < size;i++){
vec[i] = stack.pop().val;
}
return vec;
}
}
05. 重建二叉树
官方：
方法一：递归
二叉树的前序遍历顺序是：根节点、左子树、右子树，每个子树的遍历顺序同样满足前序遍历顺序。
二叉树的中序遍历顺序是：左子树、根节点、右子树，每个子树的遍历顺序同样满足中序遍历顺序。
前序遍历的第一个节点是根节点，只要找到根节点在中序遍历中的位置，在根节点之前被访问的节点都位于左子树，在根节点之后被访问的节点都位于右子树，由此可知左子树和右子树分别有多少个节点。
由于树中的节点数量与遍历方式无关，通过中序遍历得知左子树和右子树的节点数量之后，可以根据节点数量得到前序遍历中的左子树和右子树的分界，因此可以进一步得到左子树和右子树各自的前序遍历和中序遍历，可以通过递归的方式，重建左子树和右子树，然后重建整个二叉树。
使用一个 Map 存储中序遍历的每个元素及其对应的下标，目的是为了快速获得一个元素在中序遍历中的位置。调用递归方法，对于前序遍历和中序遍历，下标范围都是从 0 到 n-1，其中 n 是二叉树节点个数。
递归方法的基准情形有两个：判断前序遍历的下标范围的开始和结束，若开始大于结束，则当前的二叉树中没有节点，返回空值 null。若开始等于结束，则当前的二叉树中恰好有一个节点，根据节点值创建该节点作为根节点并返回。
若开始小于结束，则当前的二叉树中有多个节点。在中序遍历中得到根节点的位置，从而得到左子树和右子树各自的下标范围和节点数量，知道节点数量后，在前序遍历中即可得到左子树和右子树各自的下标范围，然后递归重建左子树和右子树，并将左右子树的根节点分别作为当前根节点的左右子节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
int length = preorder.length;
for (int i = 0; i < length; i++) {
indexMap.put(inorder[i], i);
}
TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
return root;
}
public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
if (preorderStart > preorderEnd) {
return null;
}
int rootVal = preorder[preorderStart];
TreeNode root = new TreeNode(rootVal);
if (preorderStart == preorderEnd) {
return root;
} else {
int rootIndex = indexMap.get(rootVal);
int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex;
TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
root.left = leftSubtree;
root.right = rightSubtree;
return root;
}
}
}
我的：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length == 0){
return null;
}
int length = preorder.length;
Map<Integer,Integer> indexMap = new HashMap<Integer,Integer>();
for(int i=0; i<length; i++){
indexMap.put(inorder[i],i);
}
TreeNode root = rebuildTree(preorder,0,length-1,inorder,0,length-1,indexMap);
return root;
}
public TreeNode rebuildTree(int[] preorder,int start_pre,int end_pre,int[] inorder,int start_in,int end_in,Map<Integer,Integer> indexMap){
if(start_pre > end_pre){
return null;
}
int rootVal = preorder[start_pre];
TreeNode root = new TreeNode(rootVal);
if(start_pre == end_pre){
return root;
} else {
int index = indexMap.get(root.val);
int leftNodes = index - start_in;
int rightNodes = end_in - index;
TreeNode leftTree = rebuildTree(preorder,start_pre+1,start_pre+leftNodes,inorder,start_in,index-1,indexMap);
TreeNode rightTree = rebuildTree(preorder,start_pre+leftNodes+1,end_pre,inorder,index+1,end_in,indexMap);
root.left = leftTree;
root.right = rightTree;
return root;
}
}
}
06. 用两个栈实现队列
class CQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public CQueue() {
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(!stack2.empty()){
return stack2.pop();
} else {
if(stack1.empty()){
return -1;
} else{
while(!stack1.empty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
07. 斐波那契数列
class Solution {
public int fib(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
int f0 = 0;
int f1 = 1;
int fn = 0;
for(int i=1; i<n;i++){
fn = (f0 + f1) % 1000000007;
f0 = f1;
f1 = fn;
}
return fn;
}
}
08. 青蛙跳台阶问题
类似于斐波那契数列
class Solution {
public int numWays(int n) {
if(n == 1 || n==0){
return 1;
}
if(n == 2){
return 2;
}
int fn_1 = 1;
int fn_2 = 2;
int fn_3 = 0;
for(int i=2; i<n; i++){
fn_3 = (fn_1+fn_2) % 1000000007;
fn_1 = fn_2;
fn_2 = fn_3;
}
return fn_3;
}
}
09. 旋转数组的最小数字
class Solution {
public int minArray(int[] numbers) {
int index1 = 0;
int index2 = numbers.length-1;
int indexMid;
if(numbers[index1] < numbers[index2]){
return numbers[index1];
}
while((index2-index1) > 1){
indexMid = (index1+index2)/2;
//如果index1和index2和indexMid的值都一样，就只能用顺序查找了
if(numbers[index1] == numbers[index2] && numbers[index2] == numbers[indexMid]){
int res = numbers[index1];
for(int i=index1+1; i<=index2; i++){
if(res > numbers[i]){
res = numbers[i];
}
}
return res;
}
if(numbers[indexMid] >= numbers[index1]){
index1 = indexMid;
} else if(numbers[indexMid] <= numbers[index2]){
index2 = indexMid;
}
}
return numbers[index2];
}
}
10. 矩阵中的路径
还有一些问题：
class Solution {
public boolean exist(char[][] board, String word) {
int rows = board.length;
int cols = board[0].length;
int wordLength = word.length();
if(wordLength>(rows*cols)){
return false;
}
boolean[][] map = new boolean[rows][cols];
boolean flag = false;;
for(int row=0; row<rows; row++){
for(int col=0; col<cols; col++){
if(board[row][col] == word.charAt(0)){
flag = hasPath(board,row,col,map,0,word);
}
if(flag == true){
return true;
}
}
}
return false;
}
public boolean hasPath(char[][] board, int i, int j, boolean[][] map, int wordIndex, String word){
if((wordIndex+1) == word.length()){
return true;
} else {
if(i>=0 && i<board.length && j>=0 && j<board[0].length && map[i][j] == false && board[i][j]==word.charAt(wordIndex)){
map[i][j] = true;
wordIndex ++;
if(hasPath(board,i+1,j,map,wordIndex,word)){
return true;
} else if(hasPath(board,i-1,j,map,wordIndex,word)){
return true;
} else if(hasPath(board,i,j+1,map,wordIndex,word)){
return true;
} else if(hasPath(board,i,j-1,map,wordIndex,word)){
return true;
} else{
return false;
}
} else{
return false;
}
}
}
}
11. 机器人的运动范围
class Solution {
public int movingCount(int m, int n, int k) {
boolean[] visited = new boolean[m*n];
int cnt = mcount(m,n,k,0,0,visited);
return cnt;
}
public int mcount(int m, int n, int k, int row, int col, boolean[] visited){
int cnt = 0;
if(check(m,n,k,row,col,visited)){
visited[row*n+col] = true;
cnt = 1+mcount(m,n,k,row-1,col,visited) + mcount(m,n,k,row+1,col,visited) + mcount(m,n,k,row,col-1,visited) + mcount(m,n,k,row,col+1,visited);
}
return cnt;
}
public boolean check(int m, int n, int k, int row, int col, boolean[] visited){
if(row>=0 && row<m && col>=0 && col<n && getSum(row,col)<=k && !visited[row*n+col]){
return true;
}
return false;
}
public int getSum(int row, int col){
int sum = 0;
while(row > 0){
sum = sum + row%10;
row = row/10;
}
while(col > 0){
sum = sum + col%10;
col = col/10;
}
return sum;
}
}
12. 剪绳子<动态规划>
class Solution {
public int cuttingRope(int n) {
if(n < 2){
return 0;
}
if(n == 2){
return 1;
}
if(n == 3){
return 2;
}
int[] products = new int[n+1];
products[0] = 0;
//这里的原因是，如果长度是1、2、3时就不要切分了，因为分了以后更小了
products[1] = 1;
products[2] = 2;
products[3] = 3;
int max = 0;
for(int i=4; i<=n; i++){
max = 0;
for(int j=1; j<=i/2; j++){
int product = products[j]*products[i-j];
if(max < product){
max = product;
}
}
products[i] = max;
}
return products[n];
}
}
13. 剪绳子<贪心算法，大数取余>
class Solution {
public int cuttingRope(int n) {
if(n < 2){
return 0;
}
if(n == 2){
return 1;
}
if(n == 3){
return 2;
}
//尽可能多的减去长度为3的绳子段
int time3 = n/3;
if(n - time3*3 == 1){
time3 = time3-1;
}
int time2 = (n-time3*3)/2;
long res = 1;
//循环取余
for(int i=0; i<time3; i++){
res = (res * 3) % 1000000007;
}
for(int i=0; i<time2; i++){
res = (res * 2) % 1000000007;
}
// long res = (long)(Math.pow(3,time3)) * (long)(Math.pow(2,time2)) % 1000000007;
return (int)res;
}
}
14. 二进制中1的个数
Java提供的位运算符有：左移( << )、右移( >> ) 、无符号右移( >>> ) 、位与( & ) 、位或( | )、位非( ~ )、位异或( ^ )
方法一：
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while(n != 0){
if((n&1) == 1){
count ++;
}
n= n>>>1;
}
return count;
}
}
牛皮方法二：
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
/*
int count = 0;
while(n != 0){
if((n&1) == 1){
count ++;
}
n= n>>>1;
}
return count;
*/
int count = 0;
while(n != 0){
count ++;
n = (n-1)&n;
}
return count;
}
}
15. 数值的整数次方
/*class Solution {
public double myPow(double x, int n) {
if((x-0.0) < 0.00000001 && n < 0){
return 0.0;
}
if(n == 0){
return 1.0;
}
if(n < 0){
double res = 1.0 / powerWithPositiveEx(x,-n);
return res;
}
double res = powerWithPositiveEx(x,n);
return res;
}
/*普通做法
public double powerWithPositiveEx(double x, int n){
double res = 1.0;
for(int i=0; i<n; i++){
res = res * x;
}
return res;
}
*//*
public double powerWithPositiveEx(double x, int n){
int cnt = (int)(Math.log(n)/Math.log(2)) - 1;
double res = x;
for(int i=1; i<cnt; i++){
res = res*res;
}
if(n%2 == 1){
res = res*x;
}
return res;
}
}*/
class Solution {
public double myPow(double x, int n) {
if(x == 0) return 0;
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}
while(b > 0) {
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;
}
return res;
}
}
16. 打印从1到最大的n位数（大数问题）
class Solution {
int res[];
int index = 0;
public int[] printNumbers(int n) {
if(n <= 0){
return new int[]{};
}
char[] number = new char[n];
res = new int[(int)Math.pow(10, n) - 1];
for(int i=0; i<10; i++){
number[0] = (char)(i+'0');
printToMax(number,n,0);
}
return res;
}
public void printToMax(char[] number, int length, int index){
if(index == length-1){
printIntoInt(number);
return;
}
for(int i=0; i<10; i++){
number[index+1] = (char)(i+'0');
printToMax(number,length,index+1);
}
}
public void printIntoInt(char[] number){
int nLength = number.length;
int result = 0;
int j = 1;
for(int i=nLength-1; i>=0; i--,j*=10){
result = result + (number[i]-'0')*j;
}
if(result != 0){
res[index] = result;
index ++;
}
}
}
17. 删除链表的节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
//没有节点
if(head == null){
return head;
}
//只有一个节点，正好要删除他
if(head.next == null && head.val == val){
return null;
}
//要删除头节点
if(head.val == val){
return head.next;
}
ListNode temp = head;
while(temp != null && temp.next != null){
if(temp.next.val == val){
temp.next = temp.next.next;
}
temp = temp.next;
}
return head;
}
}
18. 正则表达式匹配（Hard）
有递归和动态规划两种方法，这里只有递归
/*有问题
class Solution {
public boolean isMatch(String s, String p) {
if(s == null || p == null){
return false;
}
int sIndex = 0;
int pIndex = 0;
return matchCore(s,p,sIndex,pIndex);
}
public boolean matchCore(String s, String p, int sIndex, int pIndex){
if(sIndex >= s.length()-1 && pIndex >= p.length()-1){
return true;
}
if(sIndex != s.length()-1 && pIndex == p.length()-1){
return false;
}
if((pIndex+1)<p.length() && p.charAt(pIndex+1) == '*'){
if(p.charAt(pIndex) == s.charAt(sIndex) || (p.charAt(pIndex) == '.' && sIndex != s.length()-1)){
return matchCore(s,p,sIndex+1,pIndex+2) || matchCore(s,p,sIndex+1,pIndex) || matchCore(s,p,sIndex,pIndex+2);
} else {
return matchCore(s,p,sIndex,pIndex+2);
}
}
if(s.charAt(sIndex) == p.charAt(pIndex) || (p.charAt(pIndex) == '.' && sIndex != s.length()-1)){
return matchCore(s,p,sIndex+1,pIndex+1);
}
return false;
}
}
*/
class Solution {
public boolean isMatch(String A, String B) {
// 如果字符串长度为0，需要检测下正则串
if (A.length() == 0) {
// 如果正则串长度为奇数，必定不匹配，比如 "."、"ab*",必须是 a*b*这种形式，*在奇数位上
if (B.length() % 2 != 0) return false;
int i = 1;
while (i < B.length()) {
if (B.charAt(i) != '*') return false;
i += 2;
}
return true;
}
// 如果字符串长度不为0，但是正则串没了，return false
if (B.length() == 0) return false;
// c1 和 c2 分别是两个串的当前位，c3是正则串当前位的后一位，如果存在的话，就更新一下
char c1 = A.charAt(0), c2 = B.charAt(0), c3 = 'a';
if (B.length() > 1) {
c3 = B.charAt(1);
}
// 和dp一样，后一位分为是 '*' 和不是 '*' 两种情况
if (c3 != '*') {
// 如果该位字符一样，或是正则串该位是 '.',也就是能匹配任意字符，就可以往后走
if (c1 == c2 || c2 == '.') {
return isMatch(A.substring(1), B.substring(1));
} else {
// 否则不匹配
return false;
}
} else {
// 如果该位字符一样，或是正则串该位是 '.'，和dp一样，有看和不看两种情况
if (c1 == c2 || c2 == '.') {
return isMatch(A.substring(1), B) || isMatch(A, B.substring(2));
} else {
// 不一样，那么正则串这两位就废了，直接往后走
return isMatch(A, B.substring(2));
}
}
}
}
19. 表示数值的字符串
class Solution {
private int index = 0;//全局索引
private boolean scanUnsignedInteger(String str) {
//是否包含无符号数
int before = index;
while(str.charAt(index) >= '0' && str.charAt(index) <= '9')
index++;
return index > before;
}
private boolean scanInteger(String str) {
//是否包含有符号数
if(str.charAt(index) == '+' || str.charAt(index) == '-')
index++;
return scanUnsignedInteger(str);
}
public boolean isNumber(String s) {
//空字符串
if(s == null || s.length() == 0)
return false;
//添加结束标志
s = s + '|';
//跳过首部的空格
while(s.charAt(index) == ' ')
index++;
boolean numeric = scanInteger(s); //是否包含整数部分
if(s.charAt(index) == '.') {
index++;
//有小数点，处理小数部分
//小数点两边只要有一边有数字就可以，所以用||，
//注意scanUnsignedInteger要在前面，否则不会进
numeric = scanUnsignedInteger(s) || numeric;
}
if((s.charAt(index) == 'E' || s.charAt(index) == 'e')) {
index++;
//指数部分
//e或E的两边都要有数字，所以用&&
numeric = numeric && scanInteger(s);
}
//跳过尾部空格
while(s.charAt(index) == ' ')
index++;
return numeric && s.charAt(index) == '|' ;
}
}
20. 调整数组顺序使奇数位于偶数前面
class Solution {
public int[] exchange(int[] nums) {
if(nums.length == 0 ||nums.length == 1){
return nums;
}
int indexOne = 0;
int indexTwo = nums.length-1;
while(indexTwo > indexOne){
while(indexOne < indexTwo && nums[indexOne]%2 != 0){
indexOne ++;
}
while(indexTwo > indexOne && nums[indexTwo]%2 != 1){
indexTwo --;
}
if(indexTwo <= indexOne){
break;
}
int temp = nums[indexOne];
nums[indexOne] = nums[indexTwo];
nums[indexTwo] = temp;
indexOne ++;
indexTwo --;
}
return nums;
}
}
21. 链表中倒数第k个节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(head == null || k == 0){
return null;
}
ListNode tempOne = head;
ListNode tempTwo = head;
for(int i=0; i<k-1; i++){
if(tempOne.next != null){
tempOne = tempOne.next;
} else {
return null;
}
}
while(tempOne.next != null){
tempOne = tempOne.next;
tempTwo = tempTwo.next;
}
return tempTwo;
}
}
22. 反转链表
用的是一个个嵌进去的方法，参考尚学堂数据结构课
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode reverseHead = new ListNode(-1);
ListNode tempOri = head;
ListNode tempNext;
while(tempOri != null){
tempNext = tempOri.next;
tempOri.next = reverseHead.next;
reverseHead.next = tempOri;
if(tempNext == null){
break;
}
tempOri = tempNext;
tempNext = tempNext.next;
}
return reverseHead.next;
}
}
23. 合并两个排序的链表
循环迭代：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode preHead = new ListNode(-1);
ListNode temp = preHead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
temp.next = l1;
temp = temp.next;
l1 = l1.next;
} else {
temp.next = l2;
temp = temp.next;
l2 = l2.next;
}
}
if(l1 == null){
temp.next = l2;
} else{
temp.next = l1;
}
return preHead.next;
}
}
递归：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/*
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode preHead = new ListNode(-1);
ListNode temp = preHead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
temp.next = l1;
temp = temp.next;
l1 = l1.next;
} else {
temp.next = l2;
temp = temp.next;
l2 = l2.next;
}
}
if(l1 == null){
temp.next = l2;
} else{
temp.next = l1;
}
return preHead.next;
*/
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val <= l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
} else {
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
24. 树的子结构
/**
* 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 res = false;
if(A != null && B != null){
if(A.val == B.val){
res = proveSubStructure(A,B);
}
if(res == false){
res = isSubStructure(A.left,B);
}
if(res == false){
res = isSubStructure(A.right,B);
}
}
return res;
}
public boolean proveSubStructure(TreeNode A, TreeNode B){
if(B == null){
return true;
}
if(A == null){
return false;
}
if(A.val != B.val){
return false;
}
return proveSubStructure(A.left,B.left) && proveSubStructure(A.right,B.right);
}
}
25. 二叉树的镜像
/**
* 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;
}
}
