【刷题第三周】宽度优先搜索_头歌实践教学平台盲目搜索之宽度优先搜索算法答案

作者：秋刀鱼在做梦 | 2024-06-20 06:10:51

踩

头歌实践教学平台盲目搜索之宽度优先搜索算法答案

102. Binary Tree Level Order Traversal
107. Binary Tree Level Order Traversal II
637. Average of Levels in Binary Tree
111. Minimum Depth of Binary Tree
103. Binary Tree Zigzag Level Order Traversal
200. Number of Islands
133. Clone Graph

107. Binary Tree Level Order Traversal II

宽度优先搜索的基本模板，记得是用queue不是stack哦。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue <TreeNode> q = new LinkedList <>();
        q.offer(root);
        while(!q.isEmpty()){
            ArrayList<Integer> currentLevel = new ArrayList<>();
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode temp = q.poll();
                currentLevel.add(temp.val);
                if(temp.left != null){
                    q.add(temp.left);
                }
                if(temp.right != null){
                    q.add(temp.right);
                }
            }
            res.add(0, currentLevel); //跟上一题唯一的不同
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

637. Average of Levels in Binary Tree

如上，毫无变化的一个题

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue <TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            ArrayList<Integer> level = new ArrayList<>();
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode temp = q.poll();
                level.add(temp.val);
                if(temp.left != null){
                    q.offer(temp.left);
                }
                if(temp.right != null){
                    q.offer(temp.right);
                }
            }
            double avg = takeAvg(level);
            res.add(avg);
        }
        return res;
    }
    private double takeAvg(ArrayList<Integer> level){
        double sum = 0;
        for(int i = 0; i < level.size(); i++){
            sum += level.get(i);
        }
        return sum / level.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

111. Minimum Depth of Binary Tree

和FindDepth差不多，有小改动。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return helper(root);
    }
    private int helper(TreeNode root){
        if(root == null){
            return Integer.MAX_VALUE;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return Math.min(helper(root.left), helper(root.right)) + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

103. Binary Tree Zigzag Level Order Traversal

在这个BFS中，没有用到queue。因为需要LIFO的特质，我们需要用到两个stack来实现迭代求解。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList <>();
        if(root == null){
            return res;
        }
        Stack <TreeNode> currentLevel = new Stack <>();
        Stack <TreeNode> nextLevel = new Stack<>();
        Stack <TreeNode> tempStack;
        //第一行是从左到右(true)，第二行从右到左（false）
        //if true: root.right, root.left
        //if false: root.left, root.right
        boolean inOrder = true;
        currentLevel.push(root);
        while(!currentLevel.isEmpty()){
            ArrayList<Integer> level = new ArrayList<>();
            
            while(!currentLevel.isEmpty()){
                TreeNode temp = currentLevel.pop();
                level.add(temp.val);

                if(inOrder){
                    if(temp.left != null){
                        nextLevel.push(temp.left);
                    }
                    if(temp.right != null){
                        nextLevel.push(temp.right);
                    }
                } else {
                    if(temp.right != null){
                        nextLevel.push(temp.right);
                    }
                    if(temp.left != null){
                        nextLevel.push(temp.left);
                    }
                }

            }
            res.add(level);
            tempStack = currentLevel;
            currentLevel = nextLevel;
            nextLevel = tempStack;
            inOrder = inOrder == true ? false : true;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

133. Clone Graph

题目意思：要求return一个深度拷贝的Graph
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] 意味着第一个node的邻居是2，4；第二个node的邻居是1，3；第三个node的邻居是2，4；以及第四个node的邻居是1，3。
思路：用宽度优先的算法，开一个HashMap用来存对应点的node。

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
    public Node cloneGraph(Node node) {
        if(node == null){
            return node;
        }
        // Saving the original nodes and the copied nodes
        HashMap <Node, Node> visited = new HashMap <>();
        // Using a queue for the BFS implementation
        Queue <Node> queue = new LinkedList <>();
        // Start with the first node
        queue.add(node);
        // Now Visited will look like
        // node : empty
        visited.put(node, new Node (node.val, new ArrayList<>()));
        while(!queue.isEmpty()){
            // Get the first node in queue
            Node n = queue.poll();
            // Get n's neighbors
            for(Node neighbor : n.neighbors){
                // If the neighbor is not visited
                // put the neighbor into Visited, neighbor : empty
                // Add this neighbor to queue
                if(!visited.containsKey(neighbor)){
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
                    queue.offer(neighbor);
                }
                // The neighbor is already visited, add such neighbor
                // to the neighbor list of n so we save all neighbors we
                // currently have into the map.
                visited.get(n).neighbors.add(visited.get(neighbor));
            }
        }
        return visited.get(node);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】