二叉树的核心思想 - 递归 - 将问题分解为子问题
题型
- 递归遍历
- 迭代遍历
- 层序遍历 bfs：
队列 - 各种递归题目：
将问题分解为子问题 - 二叉搜索树 -
中序遍历是递增序列TreeNode* &prev指针 - 树形dp
面试经典 150 题 - 二叉树
104. 二叉树的最大深度
广度优先遍历
class Solution {
public:// 广度优先遍历int maxDepth(TreeNode* root) {if (root == nullptr) return 0;queue<TreeNode*> que;que.push(root);int result = 0;while (!que.empty()) {++result;int num = que.size();while (num--) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return result;}
};
递归
最大深度 = 1 + max(左子树最大深度， 右子树最大深度)
class Solution {
public:// 递归：最大深度 = 1 + max(左子树最大深度， 右子树最大深度)int maxDepth(TreeNode* root) {if (root == nullptr) return 0;return 1 + max(maxDepth(root->left), maxDepth(root->right));}
};
100. 相同的树
递归
树相同 --> 根节点相同 + 左子树相同 + 右子树相同
class Solution {
public:// 递归// 树相同 --> 根节点相同 + 左子树相同 + 右子树相同bool isSameTree(TreeNode* p, TreeNode* q) {if (p == nullptr && q == nullptr) {return true;} else if (p == nullptr || q == nullptr) {return false;}if (p->val != q->val) {return false;}if (isSameTree(p->left, q->left) == false) {return false;}if (isSameTree(p->right, q->right) == false) {return false;}return true;}
};
226. 翻转二叉树
递归
class Solution {
public:// 翻转二叉树 --> // 根节点的左子树 = 将右子树进行反转// 根节点的右子树 = 将左子树进行反转TreeNode *invertTree(TreeNode *root) {if (root == nullptr) return nullptr;auto left = invertTree(root->left); // 翻转左子树auto right = invertTree(root->right); // 翻转右子树root->left = right; // 交换左右儿子root->right = left;return root;}
};
⭐️⭐️112. 路径总和
回溯
class Solution {
public:// 回溯bool backtracking(TreeNode* root, int path_sum, int targetSum) { if (root == nullptr) return false;if (root->right == nullptr && root->left == nullptr) { // 到达叶子节点，终止回溯return (path_sum + root->val == targetSum);}return (backtracking(root->left, path_sum + root->val, targetSum) || \backtracking(root->right, path_sum + root->val, targetSum));}bool hasPathSum(TreeNode* root, int targetSum) {return backtracking(root, 0, targetSum);}
};
⭐️⭐️迭代
class Solution {
public:// 递归: 树 存在和为 targetSum// 也即左子树存在和为 targetSum - root->val 或者 右子树存在和为 targetSum - root->valbool hasPathSum(TreeNode* root, int targetSum) {if (root == nullptr) return false;if (root->left == nullptr && root->right == nullptr) {return (targetSum == root->val); } return (hasPathSum(root->left, targetSum - root->val) || \hasPathSum(root->right, targetSum - root->val));}
};
层序遍历
比较简单，不做讨论
面试经典 150 题 - 二叉树层次遍历
199. 二叉树的右视图
class Solution {
public:vector<int> rightSideView(TreeNode* root) {if (root == nullptr) return vector<int>{};queue<TreeNode*> que;que.push(root);vector<int> result;while (!que.empty()) {size_t n = que.size();for (size_t i = 0; i < n; ++i) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);if (i == n - 1) result.push_back(cur->val);}}return result;}
};
637. 二叉树的层平均值
class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {if (root == nullptr) return vector<double>{};queue<TreeNode*> que;que.push(root);vector<double> result;while (!que.empty()) {size_t n = que.size();double sum = 0.0;for (size_t i = 0; i < n; ++i) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);sum += cur->val;}result.push_back(sum / n);}return result;}
};
[102. 二叉树的层序遍历
](https://leetcode.cn/problems/binary-tree-level-order-traversal/?envType=study-plan-v2&envId=top-interview-150)
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if (root == nullptr) return vector<vector<int>>{};queue<TreeNode*> que;que.push(root);vector<vector<int>> result;while (!que.empty()) {size_t n = que.size();vector<int> layer(n, 0);for (size_t i = 0; i < n; ++i) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);layer[i] = cur->val;}result.push_back(layer);}return result;}
};
103. 二叉树的锯齿形层序遍历 - 写入的时候改一下索引即可
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if (root == nullptr) return vector<vector<int>>{};queue<TreeNode*> que;que.push(root);vector<vector<int>> result;bool to_right = false;while (!que.empty()) {to_right = !to_right;size_t n = que.size();vector<int> layer(n, 0);for (size_t i = 0; i < n; ++i) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);if (to_right) {layer[i] = cur->val;} else {layer[n - 1 - i] = cur->val;}}result.push_back(layer);}return result;}
};面试经典 150 题 - 二叉搜索树 - ⭐️TreeNode*& prev⭐️ - 中序遍历有序
98. 验证二叉搜索树
class Solution {
public:bool traversal(TreeNode* root, TreeNode*& prev) {if (root == nullptr) return true;if (!traversal(root->left, prev)) return false;if (prev != nullptr && prev->val >= root->val) return false;prev = root;return traversal(root->right, prev);}bool isValidBST(TreeNode* root) {TreeNode* prev = nullptr;return traversal(root, prev);}
};
530. 二叉搜索树的最小绝对差
使用数组暂存
class Solution {
public:// 二叉搜索树的特征：左子树 < 根节点 < 右子树// 中序遍历即可获得最小差值void traversal(TreeNode* root, vector<int>& vals, int& min_diff) {if (root == nullptr) return;traversal(root->left, vals, min_diff);if (!vals.empty()) min_diff = min(min_diff, root->val - vals.back()); vals.push_back(root->val);traversal(root->right, vals, min_diff);}int getMinimumDifference(TreeNode* root) {vector<int> vals;int min_diff = INT_MAX;traversal(root, vals, min_diff);return min_diff;}
};
⭐️优化 - 使用一个 prev_val 即可
class Solution {
public:// 二叉搜索树的特征：左子树 < 根节点 < 右子树// 中序遍历即可获得最小差值// 如果不想使用数组暂存的话就需要存储一个 prev 指针void traversal(TreeNode* root, TreeNode*& prev, int& min_diff) {if (root == nullptr) return;traversal(root->left, prev, min_diff);if (prev != nullptr) min_diff = min(min_diff, root->val - prev->val); prev = root;traversal(root->right, prev, min_diff);}int getMinimumDifference(TreeNode* root) {int min_diff = INT_MAX;TreeNode* prev = nullptr;traversal(root, prev, min_diff);return min_diff;}
};
230. 二叉搜索树中第 K 小的元素 - 想象用数组存储元素 - 实际只使用索引即可 - 注意终止条件
class Solution {
public:void traversal(TreeNode* root, int& val, int& count, int k) {if (root == nullptr || count >= k) return; // 递归终止条件traversal(root->left, val, count, k);++count; // 如果用数组存储元素，想象这里是数组的第 count 个数字（从0开始）if (count == k) {val = root->val;return;}traversal(root->right, val, count, k);}int kthSmallest(TreeNode* root, int k) {int val, count = 0;traversal(root, val, count, k);return val;}
};
