导航装置

难度: Hard

小扣参加的秋日市集景区共有 $N$ 个景点，景点编号为 $1$~$N$。景点内设有 $N-1$ 条双向道路，使所有景点形成了一个二叉树结构，根结点记为 `root`，景点编号即为节点值。由于秋日市集景区的结构特殊，游客很容易迷路，主办方决定在景区的若干个景点设置导航装置，按照所在景点编号升序排列后定义装置编号为 1 ~ M。导航装置向游客发送数据，数据内容为列表 `[游客与装置 1 的相对距离,游客与装置 2 的相对距离,...,游客与装置 M 的相对距离]`。由于游客根据导航装置发送的信息来确认位置，因此主办方需保证游客在每个景点接收的数据信息皆不相同。请返回主办方最少需要设置多少个导航装置。 **示例 1：** >输入：`root = [1,2,null,3,4]` > >输出：`2` > >解释：在景点 1、3 或景点 1、4 或景点 3、4 设置导航装置。 > >![image.png](https://pic.leetcode-cn.com/1597996812-tqrgwu-image.png){:height="250px"} **示例 2：** >输入：`root = [1,2,3,4]` > >输出：`1` > >解释：在景点 3、4 设置导航装置皆可。 > >![image.png](https://pic.leetcode-cn.com/1597996826-EUQRyz-image.png){:height="200px"} **提示：** - `2 <= N <= 50000` - 二叉树的非空节点值为 `1~N` 的一个排列。

Submission

运行时间: 352 ms

内存: 40.3 MB

class Solution:
    def navigation(self, root: TreeNode) -> int:
        self.res = 0
        self.s = 1 # 根是否要加一个
        def dfs(node):
            if not node:
                return False
            l = dfs(node.left)
            r = dfs(node.right)
            # 这是一个三叉
            if node.left and node.right:
                # 左右如果目前都没有，那必须左右至少有一个
                if (not l) and (not r):
                    self.res += 1
                
                # 左右不是俩都有，那无论如何根得加一个
                if not (l and r):
                    self.s = 1
                else:
                    self.s = 0
                
                return True
                
            return l or r

        l = dfs(root.left)
        r = dfs(root.right)

        # 如果左右都有，根就不需要了
        if l and r:
            return self.res
        # 如果左右只有一个，那么我们就拿那棵没有的树当父树然后 + s（对父树有需求+1，没需求不加）
        else:
            return self.res + self.s

Explain

题解通过深度优先搜索（DFS）遍历二叉树来确定最少需要设置的导航装置数量。核心思想是利用树的每个节点的左右子树的状态来确定该节点是否需要导航装置。在遍历过程中，使用递归函数dfs来处理每个节点。如果一个节点的左右子树都不存在导航装置，则至少要在一个子树上放置导航装置。如果左右子树至少有一个已经有导航装置，则根据情况设置根节点是否需要导航装置。通过这种方式，可以确保在满足题目要求的情况下，使用最少的导航装置。

时间复杂度: O(N)

空间复杂度: O(N)

class Solution:
    def navigation(self, root: TreeNode) -> int:
        self.res = 0  # 计数器，记录需要的导航装置数量
        self.s = 1  # 标记根节点是否需要导航装置
        def dfs(node):
            if not node:
                return False  # 空节点不需要导航
            l = dfs(node.left)  # 检查左子树是否有导航
            r = dfs(node.right)  # 检查右子树是否有导航
            if node.left and node.right:
                if (not l) and (not r):
                    self.res += 1  # 左右子树都没有导航，至少添加一个
                if not (l and r):
                    self.s = 1  # 左右子树不全有导航，根节点需要导航
                else:
                    self.s = 0  # 左右子树都有导航，根节点不需要额外导航
                return True  # 当前节点被覆盖
            return l or r  # 返回子树的导航装置情况
        l = dfs(root.left)
        r = dfs(root.right)
        if l and r:
            return self.res  # 如果左右子树都有导航，根节点不需额外导航
        else:
            return self.res + self.s  # 否则根据根节点的需求增加导航装置数量

Explore

在这个特定问题中，决定一个节点是否需要导航装置主要依赖于其子节点的状态，因为这是一个从下至上的决策过程。每个节点的决策仅依赖于其直接子节点的状态，而不需要考虑其父节点或兄弟节点的状态。这是因为导航设备的最优放置需要确保从任意节点访问其任一子节点时都能被导航设备覆盖。因此，每个节点的决策可以独立于其他非直接子节点的状态进行。

在当前算法的架构下，如果左右子树都没有导航装置，则在当前节点添加导航装置是必要的，以确保子节点被覆盖。这种策略是基于贪心算法，旨在立即解决未被覆盖的子树问题，通常这种策略是有效的。然而，可能存在特定的树形结构，其中通过更加全局的视角（可能需要更复杂的动态规划方法）来优化导航装置的总数。但对于大多数情况，当前的策略已经提供了一个非常接近最优的解决方案。

如果左右子树至少有一个已经有导航装置，则根节点可能不需要额外的导航装置，因为至少有一个子节点已被覆盖，从而提供给根节点所需的导航信息。题解中的逻辑通过确保每个节点或其任一子节点有导航装置，保证了游客在每个景点都能接收到数据信息。这一策略通过在树的每个必要节点上放置导航装置，确保信息的全覆盖而不重复，从而满足题目要求的效果。