【动态规划】【树形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 <= N <= 50000
二叉树的非空节点值为 1~N 的一个排列。

深度优先搜索

原理

性质一：对根节点为root1的子树，将子树外的装置移到root1，效果一样。此子树任意两个节点n1，n2。装置在x，n1和n2的距离差为：(n1 → \rightarrow →root1 → \rightarrow →x)-(n2 → \rightarrow →root1 → \rightarrow →x)    ⟺    \iff ⟺ (n1 → \rightarrow →root1)-(n2 → \rightarrow →root1)    ⟺    \iff ⟺ 此装置放到root1。当前子树根节点或树外有装置简称树外装置，当前子树根节点的子孙节点有装置称树内装置。
原则一：如果装置数量相同，优先使用树外装置，树外装置点可以共用。
性质二：如果一个子树，有两个子节点，那至少需要一个树内装置。树外装置无法区分左右节点。

性质三：子树各有一个装置，无需树内装置或树外装置，整个子树符合题意。
n1,N1来自左子树，n2,N2来自右子树，N1和N2各有一个装置。反证法证明，假定来两个距离都相等。即：
。 { n 1 → p 1 → N 1 = = n 2 → r o o t 1 → N 1 到 N 1 的距离相等 n 1 → r o o t 1 → N 2 = = n 2 → p 2 → N 2 到 N 2 的距离相等 \begin{cases} n1\rightarrow p1 \rightarrow N1 == n2 \rightarrow root1 \rightarrow N1 &到N1的距离相等 \\ n1\rightarrow root1 \rightarrow N2 == n2 \rightarrow p2 \rightarrow N2 &到N2的距离相等 \\ \end{cases} {n1→p1→N1==n2→root1→N1n1→root1→N2==n2→p2→N2​到N1的距离相等到N2的距离相等​
→ { n 1 − > r o o t 1 > n 2 − > r o o t 1 n 1 − > r o o t 1 < n 2 − > r o o t 1 矛盾 \rightarrow \begin{cases} n1->root1 > n2->root1\\ n1->root1 < n2->root1 \\ \end{cases} 矛盾 →{n1−>root1>n2−>root1n1−>root1<n2−>root1​矛盾
性质四：子树各有一个装置，无需树内装置或树外装置。当前子树内任意一节点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 < r o o t 1 → N 1 ∴ n 1 → p 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 < root1 \rightarrow N1 \\ \therefore n1 \rightarrow p1 > 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→N1<root1→N1∴n1→p1>n2→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 < n 1 → r o o t 1 P → N 1 < r o o t → N 1 → { n 1 到 N 1 的距离 < n 1 → r o o t 1 → N 1 \begin{cases} n1\rightarrow P < n1 \rightarrow root1 \\ P \rightarrow N1 < root \rightarrow N1 \end{cases}\rightarrow \begin{cases} n1到N1的距离 < n1\rightarrow root1 \rightarrow N1 \end{cases} {n1→P<n1→root1P→N1<root→N1​→{n1到N1的距离<n1→root1→N1​
→ → → → → → → → → → n 1 和 n 2 到 r o o t 1 的距离相同 n 1 到 N 1 的距离 < n 2 → r o o t 1 → N 1 ( n 2 到 N 1 的距离） \Large^{n1和n2到root1的距离相同}_{\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow\rightarrow} \normalsize n1到N1的距离 < n2\rightarrow root1 \rightarrow N1(n2到N1的距离） →→→→→→→→→→n1和n2到root1的距离相同​n1到N1的距离<n2→root1→N1(n2到N1的距离）
性质六:如果左（右）子树有一个有装置，左右子树符合题意。那么有树外装置，树内节点和任意节点都符合题意。n1是树内节点，n2是树外节点。N1是树内装置，N2是树外装置。n1和N1的最近公共祖先是p1，n2和N2的最近公共祖先是 p2,n2和root1的最近公共祖先p3。反证发：假定n1和n2到N1和N2的距离相同。即：
n 1 → p 1 → N 1 = = n 2 → p 3 → r o o t 1 → N 1 式子一 n 1 → r o o t 1 → N 2 = = n 2 → p 2 → N 2 式子二 式子一 → n 1 − > r o o t 1 > n 2 → p 3 → r o o t 1 n 1 → r o o t 1 → N 2 > n 2 → p 3 → r o o t 1 → N 2 大于等于 n 2 → N 2 ( n 2 直达 N 2 一定不慢与需要经过 p 3 , r o o t 1 ) n1\rightarrow p1 \rightarrow N1 == n2 \rightarrow p3 \rightarrow root1 \rightarrow N1 式子一 \\ n1 \rightarrow root1 \rightarrow N2 == n2 \rightarrow p2 \rightarrow N2 式子二\\ 式子一 \rightarrow n1->root1> 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<bool, int> 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++**实现。