二叉树的深度

剑指 Offer 55 - I. 二叉树的深度 - 力扣(Leetcode)

题目要求

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

例如:

给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

提示:

节点总数 <= 10000

思路分析

递归

  1. f(root)功能:计算当前节点的深度;
  2. 关系式:f(root) = max(f(left),f(right))+1;
  3. 初始值:root = null,return 0;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
// 特殊情况
if(root == null) return 0;
// 计算左右子树
int left = maxDepth(root.left);
int right = maxDepth(root.right);

return Math.max(left,right)+1;
}
}

平衡二叉树

剑指 Offer 55 - II. 平衡二叉树 - 力扣(Leetcode)

题目要求

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

例子:1

给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

返回 true

例子2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

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

返回 false

提示:

  • 0 <= 树的结点个数 <= 10000

思路分析

递归

先判断左右子树的高度是否相等,然后递归判断左右子树的左右子节点高度是否相等;最后进行剪枝,在计算高度后就判断它是否为平衡二叉树,去掉重复的计算,提升计算效率;

代码实现

时间O(n) 空间O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
// 特殊情况
if(root == null) return true;
// 判断是否为-1
if(maxDepth(root) == -1){
return false;
}else{
return true;
}
}
// 计算高度
public int maxDepth(TreeNode root){
// 特殊情况
if(root == null) return 0;
// 计算左子树
int left = maxDepth(root.left);
// 判断是否为-1
if(left == -1) return -1;
// 计算右子树
int right = maxDepth(root.right);
// 判断是否为-1
if(right == -1) return -1;
// 优化:在这里判断它是否为平衡二叉树 返回-1表示不符合条件
if(Math.abs(left - right) >1) return -1;

return Math.max(left,right)+1;
}
}

数组中数字出现的次数

剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣(Leetcode)

题目要求

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

例子:

1
2
3
4
5
输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

提示:

  • 2 <= nums.length <= 10000

思路分析

位运算定理

  • a异或a = 0;
  • a异或b异或c = a异或(b异或c);

例题:如果一个数组中除了一个数字外,其它数字都出现了两次,让你找出哪个只出现了一次的数字?

我们只需要让数组中所有数字都进行异或,那么相同的数字进行抵消,最后剩余的数字就是要找的数字;

步骤分析

因为该题有两个只出现了一次且不相同的数,假设两个只出现了一次的数分别为x和y:

  1. 让数组中所有数进行异或,最后得到:x异或y=z;
  2. 求出x和y是第几个二进制位不相等的;
  3. 定义m同z进行相与位运算,直到m与z相遇结果位1,否则一直将m左移一位;
  4. 使用找到的值同原数组的值进行相与操作,将结果等于0的放入一个数组,结果等于1的放入另一个数组,就可以将数值x和y分到两个数组中,而问题由找出两个只出现一次的不同的数值,变为找出一个只出现一次的不同的数值;
  5. 对两个数组分别进行异或操作,就能找到x和y;

代码实现

时间O(n) 空间O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int[] singleNumbers(int[] nums) {
// 定义并求出z
int z = 0;
for(int i=0;i<nums.length;i++){
z = z ^ nums[i];
}
// 定义并求出m
int m = 1;
// m和z相与,如果结果位0,就将m左移一位
while((m & z) == 0){
m = m << 1;
}

// 求x和y
int x = 0,y = 0;
for(int i=0;i<nums.length;i++){
if((nums[i] & m) == 0){
// 放入结果为0的子数组,同时用异或统计x
x = x ^ nums[i];
}else{
// 放入结果为1的子数组,同时用异或统计y
y = y ^ nums[i];
}
}
// 返回数组
return new int[]{x,y};
}
}

数组中数字出现的次数Ⅱ

剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣(Leetcode)

题目要求

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

例子:

1
2
3
4
5
输入:nums = [3,4,3,3]
输出:4

输入:nums = [9,1,7,9,7,9,7]
输出:1

提示:

  • 1 <= nums.length <= 10000
  • 1 <= nums[i] < 2^31

思路分析

位运算

将数组中数字的每一位中1出现的次数相加,然后对3取余,将结果用一个数组(32位)保存,最后将二进制翻译为十进制即可;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int singleNumber(int[] nums) {
// 定义32位数组
int[] res = new int[32];
int m = 1;
int sum = 0;

// 统计0和1
for(int i=0;i<32;i++){
for(int j=0;j<nums.length;j++){
if((nums[j] & m) !=0){
res[i]++;
}
}
// 对3取余
res[i] = res[i] % 3;
// 翻译为十进制
sum = sum + res[i] * m;
// m向左移动一位
m = m << 1;
}
return sum;
}
}

和为s的两个数字

剑指 Offer 57. 和为s的两个数字 - 力扣(Leetcode)

题目要求

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

例子:

1
2
3
4
5
输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]

输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

思路分析

双指针

  1. 定义ij两个指针,一个指向数组最左边,一个指向数组最右边;
  2. 如果nums[i]+nums[j] > target,那么需要向左移动,j--;
  3. 如果nums[i]+nums[j] < target,那么需要向右移动,i++;
  4. 最后nums[i]+nums[j] = target,找到了,返回即可;

代码实现

时间O(n) 空间O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int[] twoSum(int[] nums, int target) {
// 特殊情况
if(nums == null || nums.length <2){
return new int[0];
}
// 定义i和j两个指针
int i = 0,j = nums.length-1;
// 循环,通过关系式判断
while(i<j){
if(nums[i] + nums[j] > target){
j--;
}else if(nums[i] + nums[j] < target){
i++;
}else{
return new int[]{nums[i],nums[j]};
}
}
return new int[0];
}
}