1.问题描述
天气越来越冷了，村子里有留守老人缺少照顾，会在这个冬天里挨冻，小华想运用自己的知识帮帮他们。已知村庄里每户人家作为一个节点，这些节点可以组成一个二叉树。我们可以在二叉树的节点上供应暖炉，每个暖炉可以为该节点的父节点、自身及其子节点带来温暖。给定一棵二叉树，求使个村庄都暖和起来至少需要供应多少个暖炉？
注意
输入为一个数组，按层遍历顺序描述二叉树的节点情况。值为 1，代表存在一个节点，值为 0，代表不存在该节点。
示例1
输出最少暖炉供应数量。
输入样例
1, 1, 0, 1, 1
输出样例
1
提示
树的节点数的范围是 [1, 1000]。
难度等级
中等
题目链接
二叉树供暖问题
2.解题思路
这道二叉树供暖的问题，和LeetCode的监控二叉树问题很像，或者说核心逻辑一模一样，大家有兴趣的话，也可以先去看一下LeetCode的监控二叉树的那道题，我的专栏里也有。我就不贴链接了，哈哈哈哈哈。
说是二叉树问题，但题目一开始给我们的是一个存储层序遍历的数组，1代表节点存储，0代表节点不存在。直接对数组进行操作的话，说实话，不好操作，很麻烦，所以我选择了将数组转化成二叉树来做题，毕竟题目也说了这是个二叉树问题。
首先，定义一个基本的节点，包含左右节点和一个构造方法。
//树节点
class Node{int data;Node left;Node right;public Node(int data){this.data = data;left = null;right = null;}
}接着，我们要来用一个方法解决如何将层序遍历数组转化为二叉树的问题。
如果数组本身长度为0，那树根本就不存在，直接返回空树即可。如果数组长度不为0，那么就可以认真来构建二叉树了。层序遍历数组的第一个元素就是树的根节点，所以我们可以先把根节点创建出来。
if (nodes == null || nodes.length == 0) {return null;}//构建根节点Node root = new Node(nodes[0]);接着，不知道大家记不记得，对二叉树进行非递归的层序遍历时，我们会用到一个队列来进行辅助遍历，这里我们要来还原二叉树时，也要用一个队列来辅助我们构建，与遍历时差不多，只不过一个是取，一个是放罢了。
我们将根节点放入队列中，再定义一个指针来记录我们构建到数组中的哪个元素之后，就可以开始层序构建了。
//创建一个队列用于存储节点Queue<Node> queue = new LinkedList<>();queue.offer(root);//从数组的第二个元素开始int i = 1;从队列中取出一个节点，构造它的左右节点。在保证数组没有越界的情况下，取出指针所指向的元素，如果为1说明有节点，进行构造；0说明没有节点，跳过。并将构造好的节点继续存入队列中，同时移动数组指针。
//从队列中取出一个节点Node current = queue.poll();//处理左子节点if(i < nodes.length && nodes[i] == 1){current.left = new Node(nodes[i]);queue.offer(current.left);}//移动指针i++;//处理右子节点if(i < nodes.length && nodes[i] == 1){current.right = new Node(nodes[i]);queue.offer(current.right);}//移动指针i++;层序构造完成后，将二叉树的根节点返回。
return root;构造完二叉树之后，我们就可以开始计算暖炉的个数了。我们要用贪心的思想来解决，因为暖炉可以覆盖上下三层，如果我们在叶子节点放置暖炉的话，就会浪费掉一层，从贪心的角度是不可能这么做的，所以我们只能在非叶子节点放置暖炉。
//根据层序遍历的数组构造二叉树Node root = buildTree(nodes);既然不能在叶子节点放置暖炉，那我们就得确定某个节点是否为叶子结点，也就是要判断该节点的两个子节点是否为空，再来做其他考虑，所以我们用到的树的遍历方式是后序遍历。
接着，我们来分析一下，每一个节点都有可能是什么状态。首先，节点可能是安装了暖炉的状态，我们标记0；其次，节点还可能是供暖的状态(没有暖炉)，我们标记为1；最后，节点还可能是没有被供暖的状态，我们标记为2。顺便定义一个变量来存储所需暖炉的数量。
//后序遍历//每个节点有三种情况//0 -> 安装暖炉 1 -> 已供暖 2 -> 未供暖//记录暖炉个数static int result = 0;我们已经清楚了，叶子节点不能安装暖炉，也就是叶子节点不可能为0，每一个叶子节点都得被供暖，所以叶子节点的状态肯定是供暖的状态(1)。接着，我们要来分析一下，空节点要标记为什么状态。
假设空节点标记为安装暖炉的状态(0)，那对于只有一个叶子结点的父节点来说，它是被供暖的，那么暖炉会被安装到叶子结点的爷爷节点那里，这样实际上，叶子节点是没有被供暖到的，所以这种情况排除。
假设空节点标记为未供暖的状态(2)，那么叶子节点有两个空节点，那按照每个节点都要供暖的逻辑，我们会在叶子结点安装暖炉，这不符合我们一开始的贪心思想。
假设空节点标记为供暖的状态(1)，那么按照每个节点都要供暖的逻辑，我们可以不用管这个节点了，因为它已经供暖了。因此，我们得出来空节点标记为1的结论。
接着，我们就可以开始递归后序遍历了。递归的结束条件是遇到空节点返回供暖的状态(1)。接着递归左子节点和右子节点，分别或者左右两个子节点的状态，根据左右两个子节点的状态，判断当前节点的状态。
//空节点的情况为被供暖if(root == null){return 1;}//左int left = postorder_traversal(root.left);//右int right = postorder_traversal(root.right);如果左右节点都被供暖了，那么当前节点就未被供暖，需要父节点安装暖炉来供暖当前节点，返回未供暖的状态(2)。
//如果两个叶子节点都已供暖if(left == 1 && right == 1){//返回当前节点未供暖return 2;}如果左右节点其中有一个节点未被供暖，那么当前节点就必须安装暖炉来供暖子节点，返回安装暖炉的状态(0)。
//如果两个叶子节点有一个未供暖if(left == 2 || right == 2){//安装暖炉给叶子节点供暖result++;return 0;}如果左右节点其中有一个节点安装暖炉，那么当前节点已被供暖，返回供暖的状态(1)。
//如果两个叶子节点其中一个安装了暖炉if(left == 0 || right == 0){return 1;}后序遍历结束之后，我们可能会出现根节点刚好未被供暖的情况，所以我们得多加一步判断，如果根节点未被供暖，我们还要多加一个暖炉。
//判断根节点是否已经供暖if(postorder_traversal(root) == 2){result++;}最后，将暖炉的数量返回即可。
return result;3.代码展示
import java.util.LinkedList;
import java.util.Queue;
//树节点
class Node{int data;Node left;Node right;public Node(int data){this.data = data;left = null;right = null;}
}
public class Main {//记录暖炉个数static int result = 0;public static int solution(int[] nodes) {// Please write your code here//因为result是静态变量，所以每次调用该方法时都初始化为0比较好//防止沿用之前的暖炉个数result = 0;//根据层序遍历的数组构造二叉树Node root = buildTree(nodes);//判断根节点是否已经供暖if(postorder_traversal(root) == 2){result++;}return result;}//后序遍历//每个节点有三种情况//0 -> 安装暖炉 1 -> 已供暖 2 -> 未供暖public static int postorder_traversal(Node root){//空节点的情况为被供暖if(root == null){return 1;}//左int left = postorder_traversal(root.left);//右int right = postorder_traversal(root.right);//根//如果两个叶子节点都已供暖if(left == 1 && right == 1){//返回当前节点未供暖return 2;}//如果两个叶子节点有一个未供暖if(left == 2 || right == 2){//安装暖炉给叶子节点供暖result++;return 0;}//如果两个叶子节点其中一个安装了暖炉if(left == 0 || right == 0){return 1;}//实际上不会走到这一步，上面已经将所有情况都考虑了return 1;}//根据层序遍历的数组构建二叉树public static Node buildTree(int[] nodes) {if (nodes == null || nodes.length == 0) {return null;}//构建根节点Node root = new Node(nodes[0]);//创建一个队列用于存储节点Queue<Node> queue = new LinkedList<>();queue.offer(root);//从数组的第二个元素开始int i = 1;while(!queue.isEmpty() && i < nodes.length){//从队列中取出一个节点Node current = queue.poll();//处理左子节点if(i < nodes.length && nodes[i] == 1){current.left = new Node(nodes[i]);queue.offer(current.left);}//移动指针i++;//处理右子节点if(i < nodes.length && nodes[i] == 1){current.right = new Node(nodes[i]);queue.offer(current.right);}//移动指针i++;}return root;}public static void main(String[] args) {// You can add more test cases hereint[] nodes1 = {1, 1, 0, 1, 1};int[] nodes2 = {1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1};int[] nodes3 = {1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1};System.out.println(solution(nodes1) == 1);System.out.println(solution(nodes2) == 3);System.out.println(solution(nodes3) == 3);}
}
4.总结
这道题的关键是将层序遍历数组转化为一颗二叉树，接着用贪心的思想进行分析遍历。每个节点的状态有三种情况，依次是安装暖炉、被供暖和未被供暖。叶子节点不可能安装暖炉，同时空节点默认为已经被供暖，仔细分析这三种情况，并对节点做出相应的处理即可解决这道题了。好了，这道题啰嗦得有点多了，我就不bb了。祝大家刷题愉快~
![YOLOv11融合ICCV[2023]动态蛇形卷积Dynamic模块及相关改进思路|YOLO改进最简教程](https://i-blog.csdnimg.cn/direct/7ef3a055670844588e06284729373cf5.png)
