513. 找树左下角的值 / 剑指 Offer II 091. 粉刷房子

513. 找树左下角的值【中等题】【每日一题】

思路：【BFS】

BFS模板题，见代码注释。

代码：

/** * 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) {
    
        //定义一个队列来存储节点
        Queue<TreeNode> queue = new ArrayDeque<>();
        //首先将根节点加入队列
        queue.offer(root);
        //定义当前层的最左侧节点值，初始状态当前层只有一个根节点，因此ans初始化为根节点的值
        int ans = root.val;
        //当队列不为空时，遍历二叉树的每一层节点
        while (!queue.isEmpty()){
    
            //先求出当前队列的大小，即当前层的节点数
            int size = queue.size();
            //更新ans为当前层的最左侧节点值
            ans = queue.peek().val;
            //依次取出当前层的所有节点
            for (int i = 0; i < size; i++) {
    
                //取出队列头部节点
                TreeNode node = queue.poll();
                //如果头部节点有左子节点，就将左子节点添加到队列尾部
                if (node.left != null){
    
                    queue.offer(node.left);
                }
                //如果头部节点有右子节点，就将右子节点添加到队列尾部
                if (node.right != null){
    
                    queue.offer(node.right);
                }
            }
        }
        //二叉树层序遍历结束时，ans即为最后一层的最左侧节点值
        return ans;
    }
}

---

剑指 Offer II 091. 粉刷房子【中等题】

思路：【动态规划】

求出每个房子对应的每个颜色的动态转移方程，使用三阶dp数组存储。
最后将第n-1号房子的三个颜色的最小花费的最小值返回即可。

代码：

class Solution {
    
    public int minCost(int[][] costs) {
    
        int n = costs.length;
        //定义三阶dp数组存储每个房子刷不同颜色需要的花费
        int[][] dp = new int[n][3];
        //初始化dp[0] 
        //第0号房子刷0号颜色的最小花费就是cost[0][0]
        dp[0][0] = costs[0][0];
        //第0号房子刷1号颜色的最小花费就是cost[0][1]
        dp[0][1] = costs[0][1];
        //第0号房子刷2号颜色的最小花费就是cost[0][2]
        dp[0][2] = costs[0][2];
        //从第1号房子开始遍历，根据动态转移方程来求出每个房子刷不同颜色的花费
        for (int i = 1; i < n; i++) {
    
            //第i号房子刷0号颜色的最小花费为 第i-1号房子刷1号颜色和刷2号颜色的最小花费加上第i号房子刷0号颜色的成本
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2]) + costs[i][0];
            //第i号房子刷1号颜色的最小花费为 第i-1号房子刷0号颜色和刷2号颜色的最小花费加上第i号房子刷1号颜色的成本
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2]) + costs[i][1];
            //第i号房子刷2号颜色的最小花费为 第i-1号房子刷0号颜色和刷1号颜色的最小花费加上第i号房子刷2号颜色的成本
            dp[i][2] = Math.min(dp[i-1][0],dp[i-1][1]) + costs[i][2];
        }
        //最后返回最后一个房子 即第n-1号房子刷0、1、2号房子的最小花费的最小值
        return Math.min(dp[n-1][0],Math.min(dp[n-1][1],dp[n-1][2]));
    }
}