BFS

513. 找树左下角的值 链接：513. 找树左下角的值 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 层序遍历，每层的第一个值 看完题解后的想法 实现中遇到的困难 代码 class Solution { public: int findBottomLeftValue(TreeNode* root) { int res; if (!root) { return res; } queue<TreeNode*> q; q.push(root); while (!q.empty()) { int num = q.size(); for (int i = 0; i < num; i++) { TreeNode* cur = q.front(); q.pop(); if (i == 0) { res = cur->val; } if (cur->left) { q.push(cur->left); } if (cur->right) { q.push(cur->right); } } } return res; } }; 112. 路径总和 链接：112. 路径总和 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 DFS+回溯；栈自带回溯； ...

226. 翻转二叉树 链接：226. 翻转二叉树 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 遍历节点，然后交换节点的左右子树，DFS和BFS都能做； 看完题解后的想法 注意中序遍历因为是 左-根-右 ，在根节点交换完之后要继续访问左子树，因为已经交换了； 实现中遇到的困难 中序和后序的迭代写法还是记不牢； 代码 前序递归解： class Solution { public: TreeNode* invertTree(TreeNode* root) { dfs(root); return root; } void dfs(TreeNode* root) { if (!root) return; TreeNode* tmp = root->right; root->right = root->left; root->left = tmp; dfs(root->left); dfs(root->right); } }; 中序递归解： class Solution { public: TreeNode* invertTree(TreeNode* root) { dfs(root); return root; } void dfs(TreeNode* root) { if (!root) return; dfs(root->left); TreeNode* tmp = root->right; root->right = root->left; root->left = tmp; dfs(root->left); // 交换左右所以记得继续走左 } }; 前序迭代： ...

需要了解二叉树的种类，存储方式，遍历方式以及二叉树的定义。 文章：代码随想录 - 二叉树理论基础 DFS 144. 二叉树的前序遍历 链接：144. 二叉树的前序遍历 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 根 - 左 - 右 可以递归dfs，还可以迭代用栈模拟，还可以用Morris，但是Morris太复杂了； 看完题解后的想法 前序是"根-左-右"，弹出就访问，访问完把左右子节点压栈。节点被弹出只有一种含义：该访问了。不存在"我还要回来"的情况。 实现中遇到的困难 注意压栈的顺序是后访问的先压; 代码 递归解：(爆栈风险) class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; dfs(root, res); return res; } void dfs(TreeNode* root, vector<int>& res) { if (root == nullptr) { return ; } res.push_back(root->val); dfs(root->left, res); dfs(root->right, res); } }; 迭代解：(面试要求) class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; if (!root) { return res; } stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); res.push_back(cur->val); // 先压后访问的 if (cur->right) { st.push(cur->right); } // 再压先访问的 if (cur->left) { st.push(cur->left); } } return res; } }; 145. 二叉树的后序遍历 链接：145. 二叉树的后序遍历 文章：代码随想录 视频：B站讲解 状态：❌ 第一想法 左 - 右 - 根, 迭代解不会; ...