二叉树和递归

104. 二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) { // 递归函数定义：计算以 root 为根节点的二叉树的最大深度
        if (root == null) { // 递归终止条件
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; // 递归过程
    }
}

https://leetcode.cn/problems/maximum-depth-of-binary-tree

226. 翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) { // 递归函数定义：翻转以 root 为根节点的二叉树，返回结果是已翻转二叉树的根节点
        if (root == null) { // 递归结束条件
            return null;
        }
        // 递归过程
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

https://leetcode.cn/problems/invert-binary-tree

112. 路径总和

class Solution {
    /**
     * 递归函数定义：以 root 为根节点的二叉树中是否存在一条根节点到叶子结点的路径，其上所有节点值总和为 targetSum
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 递归结束条件
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        // 递归过程
        return hasPathSum(root.left, targetSum - root.val) 
        || hasPathSum(root.right, targetSum - root.val);
    }
}

https://leetcode.cn/problems/path-sum

257. 二叉树的所有路径

class Solution {
    /**
     * 递归函数定义：返回以 root 为根节点的二叉树的所有从根节点到叶子结点的路径
     */
    public List<String> binaryTreePaths(TreeNode root) {
        // 递归结束条件
        if (root == null) {
            return Collections.emptyList();
        }
        if (root.left == null && root.right == null) {
            return Collections.singletonList(String.valueOf(root.val));
        }
        // 递归过程
        List<String> paths = new ArrayList<>();
        for (String lPath : binaryTreePaths(root.left)) {
            paths.add(String.join("->", String.valueOf(root.val), lPath));
        }
        for (String rPath : binaryTreePaths(root.right)) {
            paths.add(String.join("->", String.valueOf(root.val), rPath));
        }
        return paths;
    }
}

https://leetcode.cn/problems/binary-tree-paths

437. 路径总和III

class Solution {
    /**
     * 递归函数定义：以 root 为根节点的二叉树中节点值之和等于 targetSum 的路径数
     */
    public int pathSum(TreeNode root, int targetSum) {
        // 递归结束条件
        if (root == null) {
            return 0;
        }
        // 递归过程
        int sum = rootSum(root, targetSum); // 以当前 root 节点开头的路径数
        sum += pathSum(root.left, targetSum); // 左子树节点值之和等于 targetSum 的路径数
        sum += pathSum(root.right, targetSum); // 右子树节点值之和等于 targetSum 的路径数
        return sum;
    }

    /**
     * 以 root 为根节点的二叉树从根节点开始到某个下面节点的节点值之和等于 targetSum 的路径数
     */
    private int rootSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val == targetSum ? 1 : 0;
        }
        // 递归过程
        int sum = root.val == targetSum ? 1 : 0;
        sum += rootSum(root.left, targetSum - root.val);
        sum += rootSum(root.right, targetSum - root.val);
        return sum;
    }
}

https://leetcode.cn/problems/path-sum-iii

235. 二叉搜索树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree