513. find the value in the lower left corner of the tree / Sword finger offer II 091 Paint the house

513. Find the value in the lower left corner of the tree 【 Medium question 】【 A daily topic 】

Ideas ：【BFS】

BFS The template questions , See code Notes .

Code ：

/** * 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 int findBottomLeftValue(TreeNode root) {
    
        // Define a queue to store nodes 
        Queue<TreeNode> queue = new ArrayDeque<>();
        // First, add the root node to the queue 
        queue.offer(root);
        // Defines the leftmost node value of the current layer , In the initial state, the current layer has only one root node , therefore ans Initialize to the value of the root node 
        int ans = root.val;
        // When the queue is not empty , Traverse every node of the binary tree 
        while (!queue.isEmpty()){
    
            // First, find the size of the current queue , That is, the number of nodes in the current layer 
            int size = queue.size();
            // to update ans Is the leftmost node value of the current layer 
            ans = queue.peek().val;
            // Take out all nodes of the current layer in turn 
            for (int i = 0; i < size; i++) {
    
                // Take out the queue header node 
                TreeNode node = queue.poll();
                // If the head node has a left child node , Add the left child node to the end of the queue 
                if (node.left != null){
    
                    queue.offer(node.left);
                }
                // If the head node has a right child node , Add the right child node to the end of the queue 
                if (node.right != null){
    
                    queue.offer(node.right);
                }
            }
        }
        // At the end of binary tree sequence traversal ,ans That is, the leftmost node value of the last layer 
        return ans;
    }
}

---

The finger of the sword Offer II 091. Paint the house 【 Medium question 】

Ideas ：【 Dynamic programming 】

Find out the dynamic transfer equation of each color corresponding to each house , Use third order dp Array storage .
Finally, the second n-1 The minimum value of the minimum cost of the three colors of House No. 1 can be returned .

Code ：

class Solution {
    
    public int minCost(int[][] costs) {
    
        int n = costs.length;
        // Define third order dp The array stores the cost of painting different colors for each house 
        int[][] dp = new int[n][3];
        // initialization dp[0] 
        // The first 0 House No 0 The minimum cost of No. 1 color is cost[0][0]
        dp[0][0] = costs[0][0];
        // The first 0 House No 1 The minimum cost of No. 1 color is cost[0][1]
        dp[0][1] = costs[0][1];
        // The first 0 House No 2 The minimum cost of No. 1 color is cost[0][2]
        dp[0][2] = costs[0][2];
        // From 1 House No. 1 began to traverse , According to the dynamic transfer equation, the cost of painting different colors for each house is calculated 
        for (int i = 1; i < n; i++) {
    
            // The first i House No 0 The minimum cost of No. 1 color is   The first i-1 House No 1 No. color and brush 2 The minimum cost of No. 1 color plus No i House No 0 The cost of color No 
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2]) + costs[i][0];
            // The first i House No 1 The minimum cost of No. 1 color is   The first i-1 House No 0 No. color and brush 2 The minimum cost of No. 1 color plus No i House No 1 The cost of color No 
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2]) + costs[i][1];
            // The first i House No 2 The minimum cost of No. 1 color is   The first i-1 House No 0 No. color and brush 1 The minimum cost of No. 1 color plus No i House No 2 The cost of color No 
            dp[i][2] = Math.min(dp[i-1][0],dp[i-1][1]) + costs[i][2];
        }
        // Finally return to the last house   That is to say n-1 House No 0、1、2 The minimum cost of House No 
        return Math.min(dp[n-1][0],Math.min(dp[n-1][1],dp[n-1][2]));
    }
}