111. 二叉树的最小深度

详细题解见Leetcode树

class Solution {
    int res = Integer.MAX_VALUE;

    public void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        dfs(root.left, depth + 1);
        if (root.left == null && root.right == null) {
            res = Math.min(res, depth);
        }
        dfs(root.right, depth + 1);
    }

    public int minDepth(TreeNode root) {
           if (root == null) {
            return 0;
        }
        dfs(root, 1);
        return res;
    }
}

112. 路径总和

详细题解见Leetcode回溯

class Solution {
    public boolean res = false;

    public void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            res = true;
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
    }

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        dfs(root, sum);
        return res;
    }
}

class Solution {
    public boolean dfs(TreeNode root, int nowSum, int sum) {
        if (root == null) {
            return false;
        }
        nowSum += root.val;
        if (root.left == null && root.right == null && nowSum == sum) {
            return true;
        }
        if (dfs(root.left, nowSum, sum) == true) {
            return true;
        }
        if (dfs(root.right, nowSum, sum) == true) {
            return true;
        }
        return false;
    }

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        return dfs(root, 0, sum);
    }
}

113. 路径总和 II

详细题解见Leetcode回溯

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        sum -= root.val;
        temp.add(root.val);
        if (root.left == null && root.right == null && sum == 0) {
            res.add(new ArrayList<>(temp));
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
        temp.remove(temp.size() - 1);
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        dfs(root, sum);
        return res;
    }
}

114. 二叉树展开为链表

详细题解见Leetcode树

class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode left = cur.left;
                TreeNode pre = left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                pre.right = cur.right;
                cur.right = left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

115. 不同的子序列

详细题解见Leetcode动态规划I

class Solution {
    public int numDistinct(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (i < j) {
                    continue;
                }
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[len1][len2];
    }
}