Pow(x, n)

public double myPow(double x, int n) {
        // 特殊情况预先排除
        if (x == 0 || x == 1) {
            return x;
        }
        if (x == -1) {
            if (n % 2 == 0) {
                return -x;
            } else {
                return x;
            }
        }
        // 处理极值，负极值转为正数时会溢出
        long N = n;
        // 对负数做处理
        if (N < 0) {
            x = 1/x;
            N = -N;
        }
        return fastPow(x, N);
    }

    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        // 用个变量存当前计算的值
        // 这里会发生递归取值
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }

求众数

// 解法1，先排序，直接取中间的值
public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
}
// 解法2，哈希表
public int majorityElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // 解法1，用一个map存每个数字出现的次数，超过n/2则为众数，时间复杂度为O(n)，空间复杂度O(n)
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                if (map.get(num) == nums.length / 2) {
                    return num;
                }
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        return -1;
    }
// 解法3，分治
见leetcode题解，代码较为复杂，注意点如下
// 1、切分为n个小数组，然后两两合并
// 2、如果两个数组的众数相同，则合并后的众数为任意一个数组的众数
// 3、如果不同，分别计算两数组的众数个数，较多的一个为新数组的众数

二叉树的层次遍历

// 广度优先搜索
public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        List<List<Integer>> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> curList = new ArrayList<>(size);
            for (int i = 0; i < size; i ++) {
                TreeNode curNode = queue.poll();
                curList.add(curNode.val);
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            res.add(curList);
        }
        return res;
    }
// 深度优先搜索
private List<List<Integer>> res = new ArrayList<>();
    // 二叉树的层次遍历（DFS）
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root, 0);
        return res;
    }

    public void dfs(TreeNode root, int level) {
        if (root == null) {
            return;
        }
        if (res.size() == level) {
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);

        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
    }

二叉树的最大深度

// DFS解法
private int depth = 0;
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        maxDepth(root, 0);
        return depth;
    }

    public void maxDepth(TreeNode root, int dep) {
        if (root == null) {
            depth = Math.max(dep, depth);
            return;
        }
        dep ++;
        maxDepth(root.left, dep);
        maxDepth(root.right, dep);
    }

二叉树的最小深度

// 注意这题有坑，不能只因为当前节点左右子节点任意为空即把当前节点作为最短节点
// 该题使用BFS解法会比DFS解法少很多节点的遍历
// 二叉树的最小深度（BFS）
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 1、定义一个队列，存储当前层的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 2、定义一个集合，存储已访问过的节点
        Set<TreeNode> visited = new HashSet<>();
        // 3、最小深度
        int minDepth = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            minDepth ++;

            for (int i = 0; i < size; i ++) {
                TreeNode node = queue.poll();
                visited.add(node);
                // 当前节点左右节点都为空，说明已经到达该分支最小深度
                if (node.left == null && node.right == null) {
                    return minDepth;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return minDepth;
    }