力扣hot100——二叉树
94. 二叉树的中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
while (root || stk.size()) {
while (root) {
stk.push(root);
root = root->left;
}
auto cur = stk.top();
stk.pop();
ans.push_back(cur->val);
root = cur->right;
}
return ans;
}
};class Solution {
public:
int maxDepth(TreeNode* root) {
auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {
if (root == NULL) return 0;
return max(dfs(root->left), dfs(root->right)) + 1;
};
return dfs(root);
}
};使用栈模拟
中序遍历本质是根在中，从左往右
因此一开始就先往左边找，找不到的情况下，说明可以往右边找了，然后又变成了一个子问题
104. 二叉树的最大深度
class Solution {
public:
int maxDepth(TreeNode* root) {
auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {
if (root == NULL) return 0;
return max(dfs(root->left), dfs(root->right)) + 1;
};
return dfs(root);
}
};经典模拟题
226. 翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
auto dfs = [](this auto&& dfs, TreeNode* root) -> void {
if (root == NULL) return;
TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
dfs(root->left);
dfs(root->right);
};
dfs(root);
return root;
}
};交换指针的时候注意tmp保存
101. 对称二叉树
class Solution {
public:
bool isSymmetric(TreeNode* root) {
auto dfs = [](this auto&& dfs, TreeNode* p1, TreeNode* p2) -> bool {
if ((p1 && !p2) || (!p1 && p2) || (p1 && p2 && p1->val != p2->val)) return false;
if (!p1 && !p2) return true;
return dfs(p1->left, p2->right) && dfs(p1->right, p2->left);
};
return dfs(root->left, root->right);
}
};模拟：分情况考虑即可
543. 二叉树的直径
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {
if (root->left && root->right) {
int t1 = max(dfs(root->left), 0);
int t2 = max(dfs(root->right), 0);
int t = t1 + t2 + 1;
ans = max(ans, t);
return max(t1, t2) + 1;
}
else if (root->left) {
int t = max(dfs(root->left), 0) + 1;
ans = max(ans, t);
return t;
}
else if (root->right) {
int t = max(dfs(root->right), 0) + 1;
ans = max(ans, t);
return t;
}
else {
ans = max(ans, 1);
return 1;
}
};
dfs(root);
return ans - 1;
}
};维护以root为根节点（包含在内）的单链最长
102. 二叉树的层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> v(2000);
if (root == NULL) return {};
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (q.size()) {
pair<TreeNode*, int> now = q.front();
q.pop();
auto u = now.first;
int dep = now.second;
v[dep].push_back(u->val);
if (u->left) {
q.push({ u->left , dep + 1});
}
if (u->right) {
q.push({ u->right , dep + 1});
}
}
vector<vector<int>> ans;
for (auto vec : v) {
if (vec.size()) ans.push_back(vec);
}
return ans;
}
};BFS记录深度
108. 将有序数组转换为二叉搜索树
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
auto dfs = [&](this auto&& dfs,int l, int r) -> TreeNode* {
if (l > r) return NULL;
int mid = (l + r) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = dfs(l, mid - 1);
root->right = dfs(mid + 1, r);
return root;
};
return dfs(0, nums.size() - 1);
}
};利用中序遍历的有序性，每次选择中间节点作为根节点，划分子问题
98. 验证二叉搜索树
class Solution {
public:
bool isValidBST(TreeNode* root) {
auto dfs = [](this auto&& dfs, TreeNode* root, long long l, long long r) -> bool {
if (root == NULL) return true;
if (root->val <= l || root->val >= r) return false;
return dfs(root->left, l, root->val) && dfs(root->right, root->val, r);
};
return dfs(root, LONG_MIN, LONG_MAX);
}
};函数表示考虑以
root为根的子树，判断子树中所有节点的值是否都在 (l,r) 的范围内（注意是开区间）。同时注意开long long
230. 二叉搜索树中第 K 小的元素
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
// vector<int> v;
int ans;
auto dfs = [&](this auto&& dfs, TreeNode* root) -> bool {
if (root == NULL) return false;
if (dfs(root->left)) return true;
k--;
if (k == 0) {
ans = root->val;
return true;
}
return dfs(root->right);
};
dfs(root);
return ans;
}
};利用平衡二叉树的中序遍历的有序性
199. 二叉树的右视图
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if (root == NULL) return {};
vector<int> ans;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
vector<TreeNode*> v;
while (q.size()) {
v.push_back(q.front());
q.pop();
}
ans.push_back(q.back()->val);
for (auto root : v) {
if (root->left)q.push(root->left);
if (root->right)q.push(root->right);
}
}
return ans;
}
};层序遍历每一层的最右边节点就是答案
114. 二叉树展开为链表
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* dummy = new TreeNode(0);
TreeNode* cur = dummy;
auto dfs = [&](this auto&& dfs, TreeNode* root) {
if (root == NULL) return;
cur->right = root;
cur = cur->right;
TreeNode* pl = root->left;
TreeNode* pr = root->right;
cur->left = NULL;
cur->right = NULL;
dfs(pl);
dfs(pr);
};
dfs(root);
}
};先序遍历模拟
105. 从前序与中序遍历序列构造二叉树
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int k = 0;
map<int, int> mp;
for (int i = 0; i < inorder.size(); i++)
mp[inorder[i]] = i;
auto dfs = [&](this auto&& dfs, int l, int r) -> TreeNode* {
if (l > r) return NULL;
TreeNode* root = new TreeNode(preorder[k++]);
root->left = dfs(l, mp[root->val] - 1);
root->right = dfs(mp[root->val] + 1, r);
return root;
};
return dfs(0, inorder.size() - 1);
}
};只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
每次递归构造的时候，当前先序遍历数组的当前第一个节点一定是当前子树的根节点
437. 路径总和 III
class Solution {
public:
using ll = long long;
int pathSum(TreeNode* root, ll targetSum) {
map<ll, int> mp;
ll ans = 0;
mp[0]++;
auto dfs = [&](this auto&& dfs, TreeNode* root, ll sum) {
if (root == NULL) return;
sum += root->val;
ans += mp[sum - targetSum];
mp[sum]++;
dfs(root->left, sum);
dfs(root->right, sum);
mp[sum]--;
};
dfs(root, 0);
return ans;
}
};哈希，dfs表示从根节点开始统计答案，并且结束后清除对map的影响的贡献
236. 二叉树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
unordered_map<TreeNode*, int> dep;
unordered_map<TreeNode*, TreeNode*> f;
dep[NULL] = 0;
auto dfs = [&](this auto&& dfs, TreeNode* root, TreeNode* fa) {
if (root == NULL) return;
dep[root] = dep[fa] + 1;
f[root] = fa;
dfs(root->left, root);
dfs(root->right, root);
};
dfs(root, NULL);
if (dep[p] < dep[q]) swap(p, q);
while (dep[p] != dep[q]) {
p = f[p];
}
if (p == q) return p;
while (p != q) {
p = f[p];
q = f[q];
}
return p;
}
};贪心，先跳到同一层，再往上跳直到相同
124. 二叉树中的最大路径和
class Solution {
public:
int maxPathSum(TreeNode* root) {
int ans = -1e9;
auto dfs = [&](this auto&& dfs, TreeNode* root) -> int {
if (root->left && root->right) {
int t1 = max(dfs(root->left), 0);
int t2 = max(dfs(root->right), 0);
int t = t1 + t2 + root->val;
ans = max(ans, t);
return max(t1, t2) + root->val;
}
else if (root->left) {
int t = max(dfs(root->left), 0) + root->val;
ans = max(ans, t);
return t;
}
else if (root->right) {
int t = max(dfs(root->right), 0) + root->val;
ans = max(ans, t);
return t;
}
else {
ans = max(ans, root->val);
return root->val;
}
};
dfs(root);
return ans;
}
};贪心，dfs记录从root开始，单链的最大值
注意分类讨论取最大值