MarsCode算法题之二叉树供暖问题

这道题的关键是将层序遍历数组转化为一颗二叉树，接着用贪心的思想进行分析遍历。每个节点的状态有三种情况，依次是安装暖炉、被供暖和未被供暖。叶子节点不可能安装暖炉，同时空节点默认为已经被供暖，仔细分析这三种情况，并对节点做出相应的处理即可解决这道题了。

2301_79318558

952人浏览 · 2024-11-12 16:00:00

2301_79318558 · 2024-11-12 16:00:00 发布

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 here
        int[] 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了。祝大家刷题愉快~