算法刷题记录-树(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算法找到从原点到目标点的路径。 $p a t h = [2, 3, 5, 7]$ , $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);}}
}

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);}
}