leetcode搜索

发表于 | 分类于

BFS：需要记录两层的节点，空间复杂度是指数级别的。O(2^h)，queue

DFS：空间复杂度为树的深度。O(h)，stack

BFS空间复杂度比较高，但是可以搜索最小性质。

空间复杂度 数据结构
DFS O(h)，h为树的高度 stack
BFS O(2^h)，指数级别的 queue 可以求出最短路的问题(边的权重是1)

1576072859183

111.二叉树最小深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int minDepth(TreeNode root) {
    return helper(root);
}

/**
     * 左右节点均不为空使，返回min(left,right)+1
     * 左右节点只有一个为空（left==null）时，需要返回right+1，而不是返回min(lef,right)+1
     * */
public int helper(TreeNode root){
    if(root==null){
        return 0;
    }
    int left = helper(root.left);
    int right = helper(root.right);
    if(root.left==null||root.right==null){
        return left+right+1;
    }
    return Math.min(left,right)+1;
}

279.完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。