二叉树03-遍历02

二叉树遍历

一棵树通过计算每个节点的问题得答案

节点独立平级没关系

1.一棵树不一定等于其根节点

2.一棵树等于其根节点但非原问题

所以，不能通过根节点子树原问题 判断等不等 根节点
那么如何判断呢

3.0 树的问题能不能转化为节点问题关键问题

3.1 一个节点应该计算什么问题

没错，我们大多时候连一个节点应该计算什么都不知道。

3.2 一个节点需要哪些信息才能计算问题

待定位置

02 652. 寻找重复的子树

map的使用
1.构建时查重

03 124. 二叉树中的最大路径和*

08 1325. 删除给定值的叶子节点

后序推导

09 865. 具有所有最深节点的最小子树*(推导)

具有所有最深节点的最小子树 = 包含树中所有最深节点的最小子树

包含树中最深节点的子树 与 节点的关系
搜索节点是否包含最深节点 同时返回深度。 这个需要先知道最深节点。

一棵树 = 其根节点 但 != 原问题
前序与后序的区别

11 968. 监控二叉树(真正的遍历与推导)*

监控二叉树 = 使每个节点都被监控到的最少摄像头数。
一个摄像头可以监视其父节点、自身及子节点

寻找 监控二叉树 与 一个节点的关系 关键问题
一个节点是否安装摄像头呢
没有被监控安装，被监控不安装。
因此 一个节点安装摄像头 = 节点外的监控范围
而 节点外的监控范围 != 全树的监控范围， 仅= 相邻节点的监控范围
相邻节点的监控范围 = 相邻节点是否有摄像头
相邻节点是否有摄像头 = 相邻节点是否有摄像头
没错这是个递归 即
一个节点是否安装摄像头 = 相邻节点是否安装摄像头
但这是不对的
AB两个节点相邻，那么A依赖B，B依赖A。形成死锁。
所以A不能依赖相邻节点是否安装摄像头。
上述只能说对，但对了一半。A不依赖这个依赖什么。
相邻节点分三个，A应该仅依赖子节点是否安装摄像头，而父节点则仅需知道有无。
A是否安装摄像头 依赖 三个节点是否安装摄像头 死锁
A是否安装摄像头 依赖 两个节点是否安装摄像头，另一个节点有无

题单顺序01.01(基础)

1.遇到递归套递归，则需要反思是否可以在后序位置进行优化。
2.遍历+推导，需要思考是否能在后序位置优化

01 543. 二叉树的直径

二叉树的直径: 是指树中任意两个节点之间最长路径的长度,这条路径可能经过也可能不经过根节点root
树的直径 = 任意两个节点的最长路径

任意 两点的路径 如何找到 与一个节点的关系呢 关键问题
可以观察到
任意 两点的路径 可以转化为 一个节点的路径 关键观察

但此路径并不一定是此节点的最长路径。
因此，要计算一个节点的最长路径。

树的直径 = 任意两个节点的最长路径
任意两个节点间路径 = 一个节点的路径
一个节点的最长路径 = 该节点子树深度之和

02 110. 平衡二叉树

树的平衡 = 每个节点的左右两个子树的高度差的绝对值不超过 1

03 563. 二叉树的坡度

树的坡度 = 节点的坡度之和
一个节点的坡度 = 该节点左子树的节点和与右子树节点和差的绝对值

04 1026. 节点与其祖先之间的最大差值(遍历/推导)

一个节点与其祖先的最大差值 = 仅需祖先的最大最小

05 508. 出现次数最多的子树元素和*

树的问题 = 次数最多的子树元素和
一个节点的子树元素和 = 该节点左子树的子树元素和与右子树的子树元素和*
如果一个节点的问题可以由该节点子树同样的问题推导而来，那么此时，节点并非代表节点，而是一棵树 例如 上述一个节点的元素和可以由该节点子树同样的问题推导而来，那么此时，这个和代表的就不是一个节点了，而是这棵树
但这个并非原问题，原问题是root节点次数最多，但不能由root子树同样问题推导，因此不能代表root树。

map的使用2:
构建时计算最大的v

06 687. 最长同值路径*

树的问题 = 最长的同值路径
任意两个节点的同值路径 = 一个节点的同值路径 同样的，此路径并非该节点最长同值路径
一个节点的最长同值路径 = 该节点子树同值深度之和
后序优化不能乱剪枝

07 1372. 二叉树中的最长交错路径

二叉树的最长交错路径
任意两点的交错路径 = 一个节点的交错路径。同理，此路径并非该节点最长
一个节点的最长交错路径 = 该节点子树交错深度max + 1

08 1339. 分裂二叉树的最大乘积

分裂二叉树的最大乘积 = 删除1条边，使树分裂成两棵子树。求最大的子树和的乘积。

任意 删除1条边后分裂的两棵子树 如何找到 与一个节点的子树和关系 关键问题
可以观察到关键观察
任意 删除1条边后分裂的两棵子树 可以转化 为 整棵树的和-此节点的树的和

09 2049. 统计最高分的节点数目

统计最高分的节点数目
一个节点的分数 = 将该节点的边全部删除，剩余若干个子树，这些子树大小的乘积。
任意 删除某节点全部边后 如何找到 与该节点子树大小的关系呢 关键问题
可以观察到关键观察
任意 删除任意节点全部边后的子树大小 = 该节点的子树大小 + (整棵树-该节点大小)

此题主要在于树为vector

10 979. 在二叉树中分配硬币

在二叉树中分配硬币 = 使每个节点有一枚硬币的最少移动次数

在二叉树中分配硬币 如何找到 与一个节点的关系呢 关键问题
我们可以先随便试一下
一个节点的移动次数 = 节点值 - 1
你会发现这并非最少，这会带来重复。关键观察
而重复的关键在于 一个节点已经计算过了，而另一个节点不知道，却依旧再计算一遍。关键观察
那么问题来了，一个节点的移动次数 = 多少次 才会不重复关键问题
一个节点直接计算其树的账就可省去某一节点重复计算了关键思想
一个节点的移动次数 = 节点树的账 = 树值 - 树大小
节点平级:我们会发现，根节点的账就是整棵树的账。但整棵树的账!=整棵树的最少移动次数。整棵树的账=根节点的移动次数。而整棵树的最少移动次数 = 所有节点的移动次数相加。这是节点平级的真谛

题单顺序02.02(遍历+推导_后序优化2)

06 663. 均匀树划分🔒

07 1120. 子树的最大平均值🔒

08 1245. 树的直径🔒

题单顺序02.03(综合)

反面例子

437. 路径总和 III*

02 1080. 根到叶路径上的不足节点

节点需要返回值的不能遍历

572. 另一棵树的子树 == LCR 143. 子结构判断

遍历推导，不能优化

1367. 二叉树中的列表