783. Minimum Distance Between BST Nodes
思路(DFS 中序遍历)
考虑中序遍历的性质即可
代码
class Solution {
public:
int min_diff=numeric_limits<int>::max();
int prev=numeric_limits<int>::min()+100000;
int minDiffInBST(TreeNode* root) {
inorderTraversal(root);
return min_diff;
}
void inorderTraversal(TreeNode* root){
if (root== nullptr){
return ;
}
inorderTraversal(root->left);
min_diff=min(min_diff,root->val-prev);
prev=root->val;
inorderTraversal(root->right);
}
};
814. Binary Tree Pruning
思路(DFS)
对于一个节点是否删除，有如下几种情况:
863. All Nodes Distance K in Binary Tree
思路（DFS）
首先，需要通过dfs算法找到从原点到目标点的路径。 p a t h = [ 2 , 3 , 5 , 7 ] path=[2,3,5,7] path=[2,3,5,7], k = 2 k=2 k=2。其中7为目标点然后考虑对路径的每一节点，进行下列计算:
对于从原点到目标节点的路径。由目标点至上逐级考虑：
- 对于目标点7，需要考虑所有距离目标节点距离为k的子节点(DFS)
- 对于目标上一个节点5，从7至5的距离为1,因此考虑与5距离为1的子节点，同时将7设为已访问，防止重复遍历。
- 。。。以此类推
代码
class Solution {
public:
vector<int> ans;
vector<TreeNode*> _path;
vector<TreeNode*> path;
unordered_set<int> visited;
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
_path.push_back(root);
findPath(root,target->val);
findNodes(path.back(),k);
path.pop_back();
k--;
visited.insert(target->val);
int size=path.size()-1;
for (int i = size; i >=0 ; i--) {
findNodes(path[i],k);
visited.insert(path[i]->val);
k--;
}
return ans;
}
void findPath(TreeNode* root,int target){
if (root->val==target){
for (auto curr:_path) {
path.push_back(curr);
}
return;
}
if (root->left){
_path.push_back(root->left);
findPath(root->left,target);
_path.pop_back();
}
if (root->right){
_path.push_back(root->right);
findPath(root->right,target);
_path.pop_back();
}
}
void findNodes(TreeNode* root,int distance){
if (distance==0&&!visited.count(root->val)){
ans.push_back(root->val);
visited.insert(root->val);
}
else {
if (root->left&&!visited.count(root->left->val)){
findNodes(root->left,distance-1);
}
if (root->right&&!visited.count(root->right->val)){
findNodes(root->right,distance-1);
}
}
}
};
865. Smallest Subtree with all the Deepest Nodes
思路 DFS
在遍历时带有层数信息以及路径信息即可，通过DFS遍历获取最深层的节点以及其路径，然后通过从头到尾遍历确认那一层是最后的公共节点。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
ArrayList<TreeNode> path = new ArrayList<>();
int max_depth = 0;
ArrayList<ArrayList<TreeNode>> res = new ArrayList<>();
public TreeNode subtreeWithAllDeepest(TreeNode root) {
path.add(root);
dfs(root, 1);
if (res.size() == 1) {
int len = res.get(0).size();
return res.get(0).get(len - 1);
}
TreeNode prev = null;
for (int i = 0; i < res.get(0).size(); i++) {
int first = res.get(0).get(i).val;
for (int j = 1; j < res.size(); j++) {
if (res.get(j).get(i).val != first) {
return prev;
}
}
prev = res.get(0).get(i);
}
return prev;
}
public void dfs(TreeNode node, int depth) {
if (node.left == null && node.right == null) {
if (depth < max_depth) {
return;
}
if (depth > max_depth) {
res.clear();
max_depth = depth;
}
res.add(new ArrayList<>(path));
return;
}
if (node.left != null) {
path.add(node.left);
dfs(node.left, depth + 1);
path.remove(path.size() - 1);
}
if (node.right != null) {
path.add(node.right);
dfs(node.right, depth + 1);
path.remove(path.size() - 1);
}
}
}
Complete Binary Tree Inserter
思路 双队列
定义upper为上层还有子树空间的树节点队列，next为当前层树节点队列。例如在下图中，upper存储[2，3]，next存储[4]。
upper存储[3]，next存储[4]。
当树为完全二叉树时next队列为空，例如下面的情况中，upper存储[4,5,6,7],next为空：
在我们插入时，我们只需查看upper队列中是否还有元素，若有元素在upper中，则去除队列头节点，向其中插入新的树节点，并在next中加入子节点。如果该节点左右子节点插满，则upper移除该节点。
如果upper为空，则next成为新的upper、next为空。
代码
public class CBTInserter {
Queue<TreeNode> upper;
Queue<TreeNode> next;
TreeNode root;
public CBTInserter(TreeNode root) {
upper = new LinkedList<>();
next = new LinkedList<>();
this.root = root;
upper.offer(root);
if (root.left != null) {
next.offer(root.left);
}
if (root.right != null) {
next.offer(root.right);
}
if (next.size()==2&&root.left.left==null){
upper.clear();
upper.addAll(next);
next.clear();
}
while (!next.isEmpty() && next.peek().left != null) {
int size = next.size();
Queue<TreeNode> emptyQueue = new LinkedList<>();
upper = emptyQueue;
while (size > 0) {
TreeNode node = next.poll();
if (node.left != null) {
next.offer(node.left);
}
if (node.right != null) {
next.offer(node.right);
}
if (node.left == null || node.right == null) {
upper.offer(node);
}
size--;
}
}
}
public int insert(int val) {
if (upper.isEmpty()) {
refreshQueue();
}
TreeNode first = upper.peek();
int parent_val = first.val;
if (first.left == null) {
first.left = new TreeNode(val);
next.offer(first.left);
} else {
first.right = new TreeNode(val);
next.offer(first.right);
upper.poll();
}
return parent_val;
}
public TreeNode get_root() {
return root;
}
public void refreshQueue() {
upper = next;
}
}
**968. Binary Tree Cameras
思路 贪心+DFS+状态转移
这道题目其实不是那么好理解的，题目举的示例不是很典型，会误以为摄像头必须要放在中间，其实放哪里都可以只要覆盖了就行。
这道题目难在两点：
- 需要确定遍历方式
- 需要状态转移的方程
我们之前做动态规划的时候，只要最难的地方在于确定状态转移方程，至于遍历方式无非就是在数组或者二维数组上。
需要确定遍历方式
首先先确定遍历方式，才能确定转移方程，那么该如何遍历呢？
在安排选择摄像头的位置的时候，我们要从底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的 ，这也是本道贪心的原理所在！
如何从低向上推导呢？
就是后序遍历也就是左右中的顺序，这样就可以从下到上进行推导了。
后序遍历代码如下：
int traversal(TreeNode* cur) {
// 空节点，该节点有覆盖
if (终止条件) return ;
int left = traversal(cur->left); // 左
int right = traversal(cur->right); // 右
逻辑处理 // 中
return ;
}
注意在以上代码中我们取了左孩子的返回值，右孩子的返回值，即 left 和 right， 以后推导中间节点的状态
需要状态转移的方程
确定了遍历顺序，再看看这个状态应该如何转移，先来看看每个节点可能有几种状态：
可以说有如下三种：
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖
那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？
回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。
那么空节点不能是无覆盖的状态，这样叶子节点就可以放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。
所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了
接下来就是递推关系。
那么递归的终止条件应该是遇到了空节点，此时应该返回 2（有覆盖），原因上面已经解释过了。
// 空节点，该节点有覆盖
if (cur == NULL) return 2;
递归的函数，以及终止条件已经确定了，再来看单层逻辑处理。
主要有如下四类情况：
情况1：左右节点都有覆盖
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
如图：
代码如下：
// 左右节点都有覆盖
if (left == 2 && right == 2) return 0;
情况2：左右节点至少有一个无覆盖的情况
如果是以下情况，则中间节点（父节点）应该放摄像头：
left == 0 && right == 0 - 左右节点无覆盖
left == 1 && right == 0- 左节点有摄像头，右节点无覆盖
left == 0 && right == 1- 左节点有无覆盖，右节点摄像头
left == 0 && right == 2 - 左节点无覆盖，右节点覆盖
left == 2 && right == 0 - 左节点覆盖，右节点无覆盖
这个不难理解，毕竟有一个孩子没有覆盖，父节点就应该放摄像头。
此时摄像头的数量要加一，并且 return 1，代表中间节点放摄像头。
代码如下：
if (left == 0 || right == 0) {
result++;
return 1;
}
情况3：左右节点至少有一个有摄像头
如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）
left == 1 && right == 2 左节点有摄像头，右节点有覆盖
left == 2 && right == 1 左节点有覆盖，右节点有摄像头
left == 1 && right == 1 左右节点都有摄像头
代码如下：
if (left == 1 || right == 1) return 2;
从这个代码中，可以看出，如果 left == 1, right == 0 怎么办？其实这种条件在情况 2 中已经判断过了，如图：
这种情况也是大多数同学容易迷惑的情况。
情况4：头结点没有覆盖
以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况，如图：
所以递归结束之后，还要判断根节点，如果没有覆盖，result++，代码如下：
int minCameraCover(TreeNode* root) {
result = 0;
if (traversal(root) == 0) { // root 无覆盖
result++;
}
return result;
}
代码
class Solution {
private:
int result;
int traversal(TreeNode* cur) {
// 空节点，该节点有覆盖
if (cur == NULL) return 2;
int left = traversal(cur->left); // 左
int right = traversal(cur->right); // 右
// 情况1
// 左右节点都有覆盖
if (left == 2 && right == 2) return 0;
// 情况2
// left == 0 && right == 0 左右节点无覆盖
// left == 1 && right == 0 左节点有摄像头，右节点无覆盖
// left == 0 && right == 1 左节点有无覆盖，右节点摄像头
// left == 0 && right == 2 左节点无覆盖，右节点覆盖
// left == 2 && right == 0 左节点覆盖，右节点无覆盖
if (left == 0 || right == 0) {
result++;
return 1;
}
// 情况3
// left == 1 && right == 2 左节点有摄像头，右节点有覆盖
// left == 2 && right == 1 左节点有覆盖，右节点有摄像头
// left == 1 && right == 1 左右节点都有摄像头
// 其他情况前段代码均已覆盖
if (left == 1 || right == 1) return 2;
// 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解
// 这个 return -1 逻辑不会走到这里。
return -1;
}
public:
int minCameraCover(TreeNode* root) {
result = 0;
// 情况4
if (traversal(root) == 0) { // root 无覆盖
result++;
}
return result;
}
};
1123. Lowest Common Ancestor of Deepest Leaves(与865重复)
思路 DFS
同865
代码
同865
1448. Count Good Nodes in Binary Tree
思路 BFS
每次遍历时，带着先前节点的最大值。若当前节点值大于等于先前的最大值，则结果+1，并更新最大值。递归遍历其左右子节点。
代码
class Solution {
int ans=0;
public int goodNodes(TreeNode root) {
goodNodesImpl(root,Integer.MIN_VALUE);
return ans;
}
public void goodNodesImpl(TreeNode root,int prevMax){
if (root==null){
return;
}
if (prevMax<=root.val){
ans++;
prevMax=root.val;
}
goodNodesImpl(root.left,prevMax);
goodNodesImpl(root.right,prevMax);
}
}