二叉树的深度

剑指 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. 定义i和j两个指针，一个指向数组最左边，一个指向数组最右边；
  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];
    }
}