网站视觉艺术设计及色彩搭配,服装网站建设的规模和类别,seo技术外包 乐云践新专家,网站套餐到期什么意思二叉树的核心思想 - 递归 - 将问题分解为子问题
题型
递归遍历迭代遍历层序遍历 bfs#xff1a;队列各种递归题目#xff1a;将问题分解为子问题二叉搜索树 - 中序遍历是递增序列 TreeNode* prev 指针树形dp
面试经典 150 题 - 二叉树
104. 二叉树的最大深度 广度优…二叉树的核心思想 - 递归 - 将问题分解为子问题
题型
递归遍历迭代遍历层序遍历 bfs队列各种递归题目将问题分解为子问题二叉搜索树 - 中序遍历是递增序列 TreeNode* prev 指针树形dp
面试经典 150 题 - 二叉树
104. 二叉树的最大深度 广度优先遍历
class Solution {
public:// 广度优先遍历int maxDepth(TreeNode* root) {if (root nullptr) return 0;queueTreeNode* 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:vectorint rightSideView(TreeNode* root) {if (root nullptr) return vectorint{};queueTreeNode* que;que.push(root);vectorint 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:vectordouble averageOfLevels(TreeNode* root) {if (root nullptr) return vectordouble{};queueTreeNode* que;que.push(root);vectordouble 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/?envTypestudy-plan-v2envIdtop-interview-150)
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {if (root nullptr) return vectorvectorint{};queueTreeNode* que;que.push(root);vectorvectorint result;while (!que.empty()) {size_t n que.size();vectorint 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:vectorvectorint zigzagLevelOrder(TreeNode* root) {if (root nullptr) return vectorvectorint{};queueTreeNode* que;que.push(root);vectorvectorint result;bool to_right false;while (!que.empty()) {to_right !to_right;size_t n que.size();vectorint 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, vectorint 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) {vectorint 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;}
};
