LeetCode中深度优先的相关算法题整理

Depth-First Search in LeetCode

Posted by S.L on October 2, 2019

转换升序数组为二叉搜索树(108)

因为数组是有序的,我们可以使用二分的思路,每次取mid为根,再将剩余的数据分列在左右两侧,因为二分可能会导致左右两边的个数不均衡,相差1,正好满足二叉搜索树两侧的树高度相差不超过一的限制。

public TreeNode sortedArrayToBST(int[] num) {
    if (num == null || num.length == 0) return null;
    return helper(num, 0, num.length - 1);
}

/**
 * Recursive, DFS
 * Divide into left subtree and right subtree with indices range
 * Choose mid point as the root of subtree
 */
public static TreeNode helper(int[] num, int left, int right) {
    if (left > right) return null;
    int mid = left + (right - left) / 2;
    TreeNode root = new TreeNode(num[mid]);
    root.left = helper(num, left, mid - 1); // left and mid -1
    root.right = helper(num, mid + 1, right); // mid + 1 and right
    return root;
}

路径之和(112)

注意这里使用了短路操作  
public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false; // root == null
    sum -= root.val; // update sum
    // leaf? sum == 0? left subtree? right subtree?
    return root.left == null && root.right == null && sum == 0 || hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}

路径之和2(113)

每一轮将当前轮的值从目标和中减掉,并将当前节点加入到当前计算的路径中,然后一直向叶子节点方向计算,如果到达叶子节点,且sum为0,则找到了一条路径。

注意:为了避免深度搜索中出栈后对集合引用的操作会影响以保存的结果,需要每次都拷贝一份存储。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    dfs(root, sum, new ArrayList<>(), res);
    return res;
}

public void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res) {
    if (root == null) return;
    sum -= root.val;
    
    if (root.left == null && root.right == null && sum == 0) {
        path.add(root.val);
        res.add(new ArrayList<>(path)); // 重新实例化一份新的数据
        path.remove(path.size() - 1); // 将当前层的数据从path中减掉,以便回到上一层后仍然是之前的结构
        return;
    }
    // 未到达叶子节点,把当前节点的值加入到路径中
    path.add(root.val);
    dfs(root.left, sum, path, res);
    dfs(root.right, sum, path, res);
    path.remove(path.size() - 1);
}

二叉树的高度最小值(111)

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    } 
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    if (left == 0) return right + 1;
    if (right == 0) return left + 1;
    return Math.min(left, right) + 1; // plus root
}

二叉树最大深度(104)

二叉树的深度为左子树或右子数的深度的最大值,采用递归的方式,计算子树的高度后再加1就是本层的高度。

private 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;
}

References

  • https://leetcode.com

本文首次发布于 S.L’s Blog, 作者 @stuartlau , 转载请保留原文链接.