二刷Leetcode-Days06

二叉树：

    /**
     * 迭代法实现中序前序后序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversalIterator(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        // 前序遍历顺序：中-左-右，入栈顺序：中-右-左
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            // 右（空节点不入栈）
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }

    public List<Integer> inOrderIterator(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 中序遍历顺序: 左-中-右 入栈顺序： 左-右
        while (cur != null || !stack.isEmpty()){
            // 先遍历到底层的左孩子结点
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                // 不为空，先弹出左孩子保存值，再获取右孩子值
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }

    public List<Integer> postOrderIterator(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            // 左（空节点不入栈）
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }

回溯：

     /**
     * 216. 组合总和 III
     * @param k
     * @param n
     * @return 找出所有相加之和为 n 的 k 个数的组合，只使用数字 1 到 9 且每个数字最多使用一次，不能包含相同的组合两次
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        combinationSum3_backtracking(k, n, 1, 0);
        return restlt;
    }

    public void combinationSum3_backtracking(int k, int targetSum, int start, int sum) {
        // 减枝
        if (sum > targetSum) {
            return;
        }
        if (path.size() == k) {
            if (sum == targetSum) {
                restlt.add(new ArrayList<>(path));
            }
            return;
        }
        // i的范围是固定的 1-9，所以减枝 9 - (k - path.size()) + 1
        for (int i = start; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);
            sum += i;
            // 注意i+1调整startIndex
            combinationSum3_backtracking(k, targetSum, i + 1, sum);
            path.removeLast();
            sum -= i;
        }
    }

贪心算法：

    /**
     * 376. 摆动序列
     * @param nums
     * @return
     */
    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        // 当前峰值差
        int curDiff = 0;
        // 前一次峰值差
        int preDiff = 0;
        // 统计波动次数，从第一个数开始
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            curDiff = nums[i] - nums[i - 1];
            // 如果当前差值和上一个差值为一正一负
            // 等于0的情况表示初始时的preDiff
            // 相乘≤0会存在当前值为水平的情况
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;

// 归并排序、快排