【动态规划】【树形dp】【深度优先搜索】LCP 26. 导航装置

本文涉及知识点

动���规划汇总

LCP 26. 导航装置

小扣参加的秋日市集景区共有 N 个景点，景点编号为 1~N。景点内设有 −1N−1 条双向道路，使所有景点形成了一个二叉树结构，根结点记为 root，景点编号即为节点值。

由于秋日市集景区的结构特殊，游客很容易迷路，主办方决定在景区的若干个景点设置导航装置，按照所在景点编号升序排列后定义装置编号为 1 ~ M。导航装置向游客发送数据，数据内容为列表 [游客与装置 1 的相对距离,游客与装置 2 的相对距离,…,游客与装置 M 的相对距离]。由于游客根据导航装置发送的信息来确认位置，因此主办方需保证游客在每个景点接收的数据信息皆不相同。请返回主办方最少需要设置多少个导航装置。

示例 1：

输入：root = [1,2,null,3,4]

输出：2

解释：在景点 1、3 或景点 1、4 或景点 3、4 设置导航装置。

示例 2：

输入：root = [1,2,3,4]

输出：1

解释：在景点 3、4 设置导航装置皆可。

提示：

2 n1→p1→N1==n2→root1→N1n1→root1→N2==n2→p2→N2​到N1的距离相等到N2的距离相等​ n 2 − > r o o t 1 n 1 − > r o o t 1 r o o t 1 矛盾 \rightarrow \begin{cases} n1->root1 > n2->root1\\ n1->root1 root1 \\ \end{cases} 矛盾 →{n1−>root1>n2−>root1n1−>root1root1​矛盾

性质四：子树各有一个装置，无需树内装置或树外装置。当前子树内任意一节点n1，和当前树外任意一节点n2符合题意，N1和N2是两个装置，和n1和n2的最近公共祖先p1,p2。假定距离都相等,不失一般性n1在左枝（或root1)：

∵ n 1 → p 1 → N 1 = = n 2 → r o o t 1 → N 1 到 N 1 距离相等 ∵ p 1 → N 1 n 2 → r o o t 1 ∵ n 1 → r o o t 1 > = n 1 → p 1 ∴ n 1 → r o o t 1 > n 2 → r o o t 1 ∴ n 1 → r o o t 1 → N 2 > n 2 → r o o t 1 → N 2 和假定到 N 2 距离相等矛盾 \because n1 \rightarrow p1 \rightarrow N1 == n2 \rightarrow root1 \rightarrow N1 到N1距离相等\\ \because p1 \rightarrow N1 n2 \rightarrow root1 \\ \because n1 \rightarrow root1 >= n1 \rightarrow p1 \\ \therefore n1 \rightarrow root1 > n2 \rightarrow root1\\ \therefore n1 \rightarrow root1 \rightarrow N2 > n2 \rightarrow root1 \rightarrow N2 和假定到N2距离相等矛盾 ∵n1→p1→N1==n2→root1→N1到N1距离相等∵p1→N1n2→root1∵n1→root1>=n1→p1∴n1→root1>n2→root1∴n1→root1→N2>n2→root1→N2和假定到N2距离相等矛盾

性质五：如果左（右）子树有一个有装置，左右子树符合题意。那么有树外装置就符合题意。

a,任意节点到root1的距离都大于0，所以root1不会和子节点到root1的距离相同。

b,n1来自左子树，n2来自右子树，n1和n2到root1距离相等。不失一般性，假定此装置在左子树节点N1。 N1和n1的公共祖先P。则n1到N1的距离为：n1 → \rightarrow →P → \rightarrow →N1 ,n2到N1的距离为：n2 → \rightarrow →root1 → \rightarrow →N1 ,有n1 N1都是左子树的节点，所以他们到P的距离小于到root1的距离。 { n 1 → P n2 \rightarrow p3 \rightarrow root1 \\ n1 \rightarrow root1 \rightarrow N2 > n2 \rightarrow p3 \rightarrow root1 \rightarrow N2 \\ 大于等于 n2 \rightarrow N2(n2直达N2一定不慢与需要经过p3,root1) n1→p1→N1==n2→p3→root1→N1式子一n1→root1→N2==n2→p2→N2式子二式子一→n1−>root1>n2→p3→root1n1→root1→N2>n2→p3→root1→N2大于等于n2→N2(n2直达N2一定不慢与需要经过p3,root1)

性质七：如果左右子树皆无装置，根据性质二，需要一个树内装置。不需要树外装置。

性质八：如果只有一个孩子，且孩子没有树内装置。那说明所有子孙节点都是孤子节点。需要一个树外装置，不需要树内装置。

性质六：如果根节点和树外无装置。一个子树有多个装置，另一个子树无装置。根据性质一，无法满足题目要求。

性质五: 独子树，一个装置就可以搞定，放到叶子节点或根节点。

性质六：非独子树， 如果装置放到树外或根节点，无法区分兄弟节点。如果放到兄弟及其后代上，无法区分兄弟和祖父。树外或根节点必须放到一个，树内任意位置放一个。

处理思路

独子树，返回1。

双子节点，如果后代没有双子节点，则需要新增一个装置。正棵树的根，也要一个装置。

注意： 如果根节点是双子节点忽略，因为他没祖先，无需区分。

两种情况，可以统一为：

1+ 没有后代是双子节点的双子节点。

DFS返回两个值：b1和i2。b1表示是否需要树外节点，i2表示如果有树外节点，树内需要多少节点。

一，叶子节点返回{false,0}

二， 双子节点 并且 没有子树有装置 {true,1} 两棵子树都有双子节点。

{ 单子节点返回 t u r e , 两个子树 i 2 之和 双子节点并且两个子树都有装置 f a l s e , 两个子树 i 2 之和 双子节点并且一个子树都有装置 t r u e , 两个子树 i 2 之和 → i 12 和 i 22 分别表示左只和右支的 i 2 。可以统一为： 0 ! = i 12 ∗ i 22 , 两个子树 i 2 之和 \begin{cases} 单子节点返回{ture,两个子树i2之和} \\ 双子节点 并且 两个子树都有装置 {false,两个子树i2之和} \\ 双子节点 并且 一个子树都有装置 {true,两个子树i2之和} \\ \end{cases}\\ \rightarrow i12 和i22 分别表示左只和右支的i2。可以统一为：{0!=i12*i22,两个子树i2之和} ⎩ ⎨ ⎧​单子节点返回ture,两个子树i2之和双子节点并且两个子树都有装置false,两个子树i2之和双子节点并且一个子树都有装置true,两个子树i2之和​→i12和i22分别表示左只和右支的i2。可以统一为：0!=i12∗i22,两个子树i2之和

代码

class Solution {public:int navigation(TreeNode* root) {const auto [i11, i12] = DFS(root->left);const auto [i21, i22] = DFS(root->right);if (0 == i12 + i22){return 1;}        bool b1 = (i11| i21)&&(0==i12*i22);   return  i12 + i22 +b1 ;}std::pair DFS(TreeNode* root){if (nullptr == root){return { 0,0 };}const auto [i11, i12] = DFS(root->left);const auto [i21, i22] = DFS(root->right);const int iChildCount = i12 + i22;bool b2 = (nullptr != root->left) && (nullptr != root->right);if (b2){return { 0 == i12 * i22,(b2 && (0 == iChildCount)) ? 1 : iChildCount };}return { i11 | i21, iChildCount };}};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。