算法刷题记录-树(LeetCode)

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算法找到从原点到目标点的路径。$path=[2,3,5,7]$,$k=2$。其中7为目标点然后考虑对路径的每一节点，进行下列计算:
对于从原点到目标节点的路径。由目标点至上逐级考虑：

1. 对于目标点7，需要考虑所有距离目标节点距离为k的子节点(DFS)
2. 对于目标上一个节点5，从7至5的距离为1,因此考虑与5距离为1的子节点，同时将7设为已访问，防止重复遍历。
3. 。。。以此类推

代码

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+状态转移

这道题目其实不是那么好理解的，题目举的示例不是很典型，会误以为摄像头必须要放在中间，其实放哪里都可以只要覆盖了就行。

这道题目难在两点：

1. 需要确定遍历方式
2. 需要状态转移的方程

我们之前做动态规划的时候，只要最难的地方在于确定状态转移方程，至于遍历方式无非就是在数组或者二维数组上。

需要确定遍历方式

首先先确定遍历方式，才能确定转移方程，那么该如何遍历呢？

在安排选择摄像头的位置的时候，我们要从底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的 ，这也是本道贪心的原理所在！

如何从低向上推导呢？

就是后序遍历也就是左右中的顺序，这样就可以从下到上进行推导了。

后序遍历代码如下：

    int traversal(TreeNode* cur) {// 空节点，该节点有覆盖if (终止条件) return ;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右逻辑处理                            // 中return ;}

注意在以上代码中我们取了左孩子的返回值，右孩子的返回值，即 left 和 right， 以后推导中间节点的状态

需要状态转移的方程

确定了遍历顺序，再看看这个状态应该如何转移，先来看看每个节点可能有几种状态：

可以说有如下三种：

1. 该节点无覆盖
2. 本节点有摄像头
3. 本节点有覆盖

那么问题来了，空节点究竟是哪一种状态呢？ 空节点表示无覆盖？ 表示有摄像头？还是有覆盖呢？

回归本质，为了让摄像头数量最少，我们要尽量让叶子节点的父节点安装摄像头，这样才能摄像头的数量最少。

那么空节点不能是无覆盖的状态，这样叶子节点就可以放摄像头了，空节点也不能是有摄像头的状态，这样叶子节点的父节点就没有必要放摄像头了，而是可以把摄像头放在叶子节点的爷爷节点上。

所以空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

接下来就是递推关系。

那么递归的终止条件应该是遇到了空节点，此时应该返回 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;// 情况4if (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);}
}