This week’s 5 leetcodes are:

  • 102 Sequence traversal of binary trees
  • Hierarchical traversal of binary tree ⅱ
  • Number of 547 provinces
  • 687 The longest path with the same value
  • 322 Change

102 Sequence traversal of binary trees

Topic describes

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

  • Example:
Binary tree: [3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7 Return the sequence traversal result:[[3], [9,20], [15,7]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Method a BFS

The hierarchical traversal of binary trees is actually an application of the BFS idea, implemented using a queue. But the output format for this problem is slightly different, with elements of the same layer being grouped together.

On the basis of the original level traversal code, we add two variables:

  • levelNodes: records the number of nodes at each layer. The default value is1The root node
  • index: represents the subscript of the result set, which identifies the current element asindexLayer elements (from0Start)

First, if the root node is empty, an empty list is returned. After the first queued element is queued, reduce levelNodes by 1 and add the value of the queued element to the index position in the result set.

After joining the left and right children (or leaving them empty), if levelNodes == 0 &&! Queue.isempty (), indicating that the index layer has been traversed, add index by 1, then the number of elements in the queue is the number of elements in the next layer.

In the code, two details need to be noted:

  • levelNodes == 0 && ! queue.isEmpty()This condition cannot remove the second condition, otherwise you end up with an empty set
  • index++Later,resultI’m going to add a new elementresult.add(new ArrayList<>())Or next timeresult.get(index)An out-of-bounds subscript exception is reported

The code is as follows:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {return new ArrayList<>();
        }
        // Record the number of nodes in each layer
        int levelNodes = 1;
        // Indicates the level currently traversed. Result Indicates the subscript of the result set
        int index = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        TreeNode node = null;
        queue.offer(root);
        while(! queue.isEmpty()){ node = queue.poll(); result.get(index).add(node.val); levelNodes--;if(node.left ! =null){
                queue.offer(node.left);
            }
            if(node.right ! =null){
                queue.offer(node.right);
            }
            // If you don't add it! Queue.isempty (), which ends with an extra empty subset
            if(levelNodes == 0 && !queue.isEmpty()){
                index++;
                result.add(newArrayList<>()); levelNodes = queue.size(); }}returnresult; }}Copy the code

Hierarchical traversal of binary tree ⅱ

Topic describes

Given a binary tree, return a bottom-up traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)

  • Such as:
Given a binary tree [3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7 Returns its bottom-up sequence traversal as:[[15,7], [9,20], [3]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/bi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Method a BFS

This problem is the same as 102 binary tree traversal, using the BFS idea. But this problem requires us to output from the last layer, we just need to insert the node heads of each layer into the result set.

In order to improve the efficiency of header insertion, the result set uses LinkedList and the insertion time complexity is O(1).

The code is as follows:

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null) {return new LinkedList<>();
        }
        int levelNodes = 1;
        int index = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new LinkedList<>();
        TreeNode node = null;
        result.add(new ArrayList<>());
        queue.add(root);
        while(! queue.isEmpty()){ node = queue.poll(); levelNodes--;// The node of the current layer always exists in the first element
            result.get(0).add(node.val);
            if(node.left ! =null){
                queue.add(node.left);
            }
            if(node.right ! =null){
                queue.add(node.right);
            }
            if(levelNodes == 0 && !queue.isEmpty()){
                index++;
                // Insert an empty element in the header to store the elements in the previous layer
                result.add(0.newArrayList<>()); levelNodes = queue.size(); }}returnresult; }}Copy the code

Number of 547 provinces

Topic describes

There are n cities, some of which are connected to each other, some of which are not. If city A is directly connected to city B, and city B is directly connected to city C, then city A is indirectly connected to city C.

A province is a group of directly or indirectly connected cities that do not contain other unconnected cities.

IsConnected [I][j] = 1 indicates that the ith city and the j city are directly connected, and isConnected[I][j] = 0 indicates that the two are not directly connected.

Returns the number of provinces in the matrix.

  • Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] output: 2Copy the code
  • Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]Copy the code

Source: LeetCode link: leetcode-cn.com/problems/nu… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Method a DFS

This problem can be interpreted as finding the number of connected components in the graph. Each connected component constitutes a province.

DFS’s thought is through every city, if the city has not been visited (i.e., no province), is to find whether there is interlinked with the city’s other cities, if any, to other cities for the same operation (DFS) recursive process, until a city and all are not of the cities visited are not same, The cities visited then constituted a province.

First, we need an array int[] visited to indicate whether the city has been visited. If city I has been visited, we need to change visited[I] to 1.

  • visited[i] == 1According to the firstiTen cities were visited
  • visited[i] == 0According to the firstiTen cities were not visited

The DFS recursive function is defined as follows:

/** * DFS recursive function *@paramIsConnected: NXN matrix *@paramCity: the city currently visited *@paramCities: total number of cities *@param*/
public void dfs(int[][] isConnected,int city,int cities,int[] visited){
    // Search for unvisited cities that are connected to cities
    for(int i = 0; i < cities; i++){
        if(isConnected[city][i] == 1 && visited[i] == 0) {// After accessing the city I remember to modify the access array
            visited[i] = 1;
            // Recurse for city Idfs(isConnected,i,cities,visited); }}}Copy the code

With recursive functions, we traverse the city, call recursive operations on unvisited cities, and record the number of provinces.

// DFS
public int findCircleNum(int[][] isConnected) {
    int result = 0;
    int cities = isConnected.length;
    int[] visited = new int[cities];
    for(int i = 0; i < cities; i++){
        if(visited[i] == 0){
            visited[i] = 1; dfs(isConnected,i,cities,visited); result++; }}return result;
}
Copy the code

Method two BFS

BFS is usually done in conjunction with queues, and this one is no exception.

The basic idea is the same as solution 1, also need an access array, traverse the city, if not visited, join the queue, if the queue is not empty, find the first city connected to the queue and not visited, and join the queue.

Until the queue is empty, at which point a province was found.

// Solution 2 BFS
public int findCircleNum(int[][] isConnected) {
    Queue<Integer> queue = new LinkedList<>();
    int cities = isConnected.length;
    int[] visited = new int[cities];
    int temp = 0;
    int result = 0;
    for(int i = 0; i < cities; i++){
        if(visited[i] == 0){
            queue.offer(i);
            while(! queue.isEmpty()){ temp = queue.poll(); visited[temp] =1;
                for(int j = 0; j < cities; j++){
                    if(isConnected[temp][j] == 1 && visited[j] == 0){ queue.offer(j); } } } result++; }}return result;
}
Copy the code

Solution of three union search set

And the basic template for the lookup set class is given in the 200 island count.

At the beginning, all cities have their own ancestors, traversing the isConnected matrix. If cities I and J are connected, merge them, that is, set their ancestors to the same ancestor. When traversal is complete, all cities in the same province have the same ancestor.

If root[I] = I, the number of cities in the set is the final number of provinces.

Result () = result();

// Check the set class
class UnionFind{
    private int[] root;

    public UnionFind(int[][] isConnected){
        root = new int[isConnected.length];
        for(int i = 0; i < root.length; i++){ root[i] = i; }}public void union(int x,int y){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY){
            root[rootX] = rootY;
        }
    }

    public int find(int x){
        if(x == root[x]){
            return x;
        }
        root[x] = find(root[x]);
        return root[x];
    }

    public int result(a){
        int result = 0;
        for(int i = 0; i < root.length; i++){
            if(root[i] == i){ result++; }}returnresult; }}Copy the code

Iterate through the isConnected matrix and merge if cities are connected:

// Check the set
public int findCircleNum(int[][] isConnected) {
    UnionFind uf = new UnionFind(isConnected);
    int result = 0;
    for(int i = 0; i < isConnected.length; i++){
        for(int j = i+1; j < isConnected[0].length; j++){
            if(isConnected[i][j] == 1){ uf.union(i,j); }}}return uf.result();
}
Copy the code

Since isConnected represents an undirected graph, it must be a symmetric matrix, and we only need to traverse the elements of the upper (or lower) triangle.

687 The longest path with the same value

Topic describes

Given a binary tree, find the longest path where each node has the same value. This path may or may not go through the root node.

Note: The length of the path between two nodes is represented by the number of edges between them.

  • Example 1:
Input:5 / \ 4 5 / \ 1 1 5 output: 2Copy the code
  • Example 2:
Input:1 / \ 4 5 / \ 4 4 5 Output: 2Copy the code

Note: A given binary tree has no more than 10,000 nodes. The height of the tree does not exceed 1000.

Source: LeetCode link: leetcode-cn.com/problems/lo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: binary tree recursion

This problem can be solved recursively, and the binary tree itself is a recursive structure.

During recursion, you need to constantly compare whether there is a larger same-valued path, so you define a global variable result = 0 to represent the length of the longest same-valued path that is eventually returned.

Define the recursive function int longestPath(TreeNode) that returns the larger value of the longestPath length on the left and right sides of the current subtree. The following is an implementation of the recursive function:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
    private int result = 0;
    public int longestUnivaluePath(TreeNode root) {
        longestPath(root);
        return result;
    }

    public int longestPath(TreeNode root){
        // 1. If the root node is empty, return 0
        if(root == null) {return 0;
        }
        // 2. Obtain the longest path length on both sides of the left and right subtrees
        int left = longestPath(root.left);
        int right = longestPath(root.right);
        // 3. Calculate the longest path length on both sides of the current subtreeleft = root.left ! =null && root.left.val == root.val? left + 1 : 0; right = root.right ! =null && root.right.val == root.val ? right + 1 : 0;
        // 4. Update the maximum path length with the same value
        result = Math.max(result,left + right);
        returnMath.max(left,right); }}Copy the code

Let’s look at the details of the code implementation.

First of all, let’s make it clear that a path in the tree is logically linear, there can be no crossings, and in short, it has to be one stroke.

The path length returned by the recursive function is not the longest same-valued path of the true subtree, but the larger value of the longest same-valued path of the left and right sides, including the root. In other words, the maximum same-valued path length returned by the recursive function does not include the case that spans the left and right subtrees, because it cannot form a path with the parent node.

For example, in the following binary tree, when we recurse to the first 4, the longest path of the current subtree is actually 2.

But instead of returning 2, you should return 1. Because if the parent of 4 is also 4, then the longest same-valued path will be crossed, as shown in the figure below.

So recursive functions can only return larger values of the longest path to the left and right, which is why you need a global variable result to keep track of updating the actual longest path.

When calculating the longest same-valued path as a subtree, care is also taken to determine whether the values of the left and right child nodes are equal to the current root node. In the case of the left child, if the left child is not empty and is equal to the root node, then the longest path with the same value on the left should be incremented by 1; Otherwise, the longest congruent path on the left should be 0 (path broken, discontinuous).

Result = math.max (result,left + right);

  • ifleft 和 rightBoth are not 0, indicating that the root node is equal to the left and right children, and the longest path with the same value crosses the left and right subtreesleft+rightTo compare
  • ifleft 和 rightOne of them is zeroleft+rightIt’s exactly the longest path length on the left and right side
  • ifleft 和 rightBoth are 0, indicating that the left and right children are not equal to the root node, so there is no longest path with the same value

322 Change

Topic describes

Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1.

You can think of an infinite number of each coin.

  • Example 1:
Input: Coins = [1, 2, 5], amount = 11Copy the code
  • Example 2:
Input: Coins = [2], amount = 3 Output: -1Copy the code
  • Example 3:
Input: Coins = [1], amount = 0 Output: 0Copy the code
  • Example 4:
Input: Coins = [1], amount = 1 Output: 1Copy the code
  • Example 5:
Input: Coins = [1], amount = 2 Output: 2Copy the code
  • Tip:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
Copy the code

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1 dynamic programming

If coin I is selected, the number of coins should be increased by 1, and coins should be selected to minimize the number of coins that reach the value of Amout-of-coins [I]. This is the optimal substructure of the problem.

Dp [I] is used to represent the minimum number of coins required to make up the amount of I, then the equation of state of dynamic programming is as follows:


d p [ i ] = m i n j ∈ c o i n s ( d p [ i – j ] + 1 ) dp[i] = min_{j \in coins}(dp[i – j] + 1)

With equations of state, the code is easy to implement:

// Dynamic programming
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    for(int i = 0; i < dp.length; i++){
        dp[i] = amount + 1;
    }
    dp[0] = 0;
    for(int i = 1; i <= amount; i++){
        for(int j = 0; j < coins.length; j++){
            if(i - coins[j] >= 0){
                dp[i] = Math.min(dp[i],dp[i-coins[j]] + 1); }}}return dp[amount] == amount + 1 ? -1 : dp[amount];
}
Copy the code

Note that the length of the dp array is amount + 1, and dp[0] = 0.

At initialization, dp arrays are populated with amount + 1 by default, to make it easier to compare smaller values, or integer.max_value.

If i-coins [j] < 0 in the calculation process, that is, the face value of coins is larger than the current amount, it indicates that the coins cannot be combined. In this case, no operation is performed. If all coins are larger than the amount, dp[I] will remain at amount + 1, so it can be determined that there is no combination of any amount I. Return 1.