二叉树高频题（下）
236. 二叉树的最近公共祖先
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:// 前提：节点的值唯一，p、q都在二叉树中TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {// 如果 p 和 q 中有等于 root 的，那么它们的最近公共祖先即为 root（一个节点也可以是它自己的祖先）if (root == nullptr || root == p || root == q) return root;// 递归遍历左子树，只要在左子树中找到了 p 或 q，则先找到谁就返回谁TreeNode *left = lowestCommonAncestor(root->left, p, q);// 递归遍历右子树，只要在右子树中找到了 p 或 q，则先找到谁就返回谁TreeNode *right = lowestCommonAncestor(root->right, p, q);// 当 left 和 right 均不为空时，说明 p、q 节点分别在 root 异侧, 最近公共祖先即为 rootif (left != nullptr && right != nullptr) return root;// 如果在一侧的子树中 p 和 q 都找不到，则 p 和 q 一定都在另一侧的子树中，另一侧中先遍历到的那个就是最近公共祖先return left == nullptr ? right : left;}
};
235. 二叉搜索树的最近公共祖先
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {if (root == nullptr || root == p || root == q) return root;// 都比当前根节点的值小，说明都在左子树if (root->val > p->val && root->val > q->val)return lowestCommonAncestor(root->left, p, q);// 都比当前根节点的值大，说明都在右子树if (root->val < p->val && root->val < q->val)return lowestCommonAncestor(root->right, p, q);// 在两侧，当前的根节点就是最近公共祖先return root;}
};
class Solution {
public:TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {if (root == nullptr || root == p || root == q) return root;TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right = lowestCommonAncestor(root->right, p, q);if (left == nullptr) return right;if (right == nullptr) return left;return root;}
};
113. 路径总和 II
#include <vector>using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:vector<vector<int>> res;vector<int> path;int target;void dfs(TreeNode *root, int sum) {if (root == nullptr) return;sum += root->val;if (root->left == nullptr && root->right == nullptr && sum == target) {path.emplace_back(root->val);res.emplace_back(vector<int>(path));// 回退路径path.erase(end(path));return;}path.emplace_back(root->val);if (root->left != nullptr) dfs(root->left, sum);if (root->right != nullptr) dfs(root->right, sum);// 回退路径path.erase(end(path));}vector<vector<int>> pathSum(TreeNode *root, int targetSum) {target = targetSum;dfs(root, 0);return res;}
};
class Solution {
public:vector<vector<int>> res;vector<int> path;// 记录节点对应的值在 path 中的下标unordered_map<TreeNode *, int> map;int target;void dfs(TreeNode *root, int sum) {if (root == nullptr) return;path.emplace_back(root->val);map.emplace(root, path.size() - 1);sum += root->val;if (root->left == nullptr && root->right == nullptr && sum == target) {res.emplace_back(vector<int>(path));return;}if (root->left != nullptr) {dfs(root->left, sum);// 回退路径path.erase(begin(path) + map[root->left], end(path));}if (root->right != nullptr) {dfs(root->right, sum);// 回退路径path.erase(begin(path) + map[root->right], end(path));}}vector<vector<int>> pathSum(TreeNode *root, int targetSum) {target = targetSum;dfs(root, 0);return res;}
};
110. 平衡二叉树
#include <algorithm>using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:bool balance;int depth(struct TreeNode *node) {if (!balance || node == nullptr) return 0;int left = depth(node->left);int right = depth(node->right);// 不平衡if (abs(left - right) > 1) balance = false;return max(left, right) + 1;}bool isBalanced(TreeNode *root) {balance = true;depth(root);return balance;}
};
98. 验证二叉搜索树
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:TreeNode *pre;// 中序遍历检查是否严格递增bool inorder(TreeNode *root) {if (root == nullptr) return true;if (!inorder(root->left)) return false;if (pre != nullptr && pre->val >= root->val) return false;pre = root;return inorder(root->right);}bool isValidBST(TreeNode *root) {pre = nullptr;return inorder(root);}
};
class Solution {
public:// 判断每个节点是否在他应当在的范围内bool dfs(struct TreeNode *root, long long min, long long max) {if (root == nullptr) return true;if (root->val <= min || root->val >= max) return false;return dfs(root->left, min, root->val) && dfs(root->right, root->val, max);}bool isValidBST(TreeNode *root) {return dfs(root, 0x8000000000000000, 0x7fffffffffffffff);}
};
669. 修剪二叉搜索树
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:TreeNode *trimBST(TreeNode *root, int low, int high) {if (root == nullptr) return nullptr;// 根节点超范围，返回用修剪后的子树，顶替根节点if (root->val < low) return trimBST(root->right, low, high);if (root->val > high) return trimBST(root->left, low, high);root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}
};
337. 打家劫舍 III
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:// 超时int rob(TreeNode *root) {if (root == nullptr) return 0;int money = root->val;if (root->left != nullptr)money += rob(root->left->left) + rob(root->left->right);if (root->right != nullptr)money += rob(root->right->left) + rob(root->right->right);// 返回偷 root 和不偷 root 的最大值return max(money, rob(root->left) + rob(root->right));}
};
class Solution {
public:// 记录能偷的最大值unordered_map<TreeNode *, int> dp;int robInternal(TreeNode *root) {if (root == nullptr) return 0;// 如果有就返回if (dp.find(root) != dp.end()) return dp[root];int money = root->val;if (root->left != nullptr)money += (robInternal(root->left->left) + robInternal(root->left->right));if (root->right != nullptr)money += (robInternal(root->right->left) + robInternal(root->right->right));int result = max(money, robInternal(root->left) + robInternal(root->right));dp[root] = result;return result;}int rob(TreeNode *root) {return robInternal(root);}
};
class Solution {
public:int rob(TreeNode* root) {// 返回的是不偷和偷当前节点时，能偷的最大值vector<int> result = recursive(root);return max(result[0], result[1]);}vector<int> recursive(TreeNode* root) {if (root == nullptr) return {0, 0};vector<int> res(2);vector<int> left = recursive(root->left);vector<int> right = recursive(root->right);res[0] = max(left[0], left[1]) + max(right[0], right[1]);res[1] = left[0] + right[0] + root->val;return res;}
};
