1. 矩阵中的路径
吃过晚饭，继续开始。算是一个新的专题：搜索与回溯算法。第七题，矩阵中的路径。读了题，发现应该是回溯法，尝试了好久，勉勉强强敲出来，很惊喜是时间快于百分之99.1的答案。
bool myF(vector<vector<char>> &board, string &word, int wordIndex, int x, int y);bool exist(vector<vector<char>> &board, string word) {//遍历for (int i = 0; i < board.size(); ++i) {for (int j = 0; j < board[i].size(); ++j) {if (myF(board, word, 0, i, j))return true;}}return false;}bool myF(vector<vector<char>> &board, string &word, int wordIndex, int x, int y) {//当前位置的字母是否符合if (board[x][y] != word[wordIndex])return false;//最后一个也满足，成功if (word.size() - 1 == wordIndex)return true;//回溯用char temp = board[x][y];board[x][y] = 0;wordIndex++;//走的通if ((x > 0 && myF(board, word, wordIndex, x - 1, y)) ||(y > 0 && myF(board, word, wordIndex, x, y - 1)) ||(x < board.size() - 1 && myF(board, word, wordIndex, x + 1, y)) ||(y < board[0].size() - 1 && myF(board, word, wordIndex, x, y + 1)))return true;//走不通,回溯board[x][y] = temp;return false
2. 树的子结构
开始第八题：树的子结构。想法：首先遍历第一棵树，看看第二根数的根节点在不在第一棵树上面。如果在，第二步就是去看以这个点为根节点的树是否包括第二棵树，方法显而易见用回溯。
IDE优化，判断树是否为NULL时候，会提醒改为nullptr。
有点沮丧，通过48个中的47个！先贴代码，晚上回来看，去锻炼下身体。
bool myF(TreeNode *A, TreeNode *B) {if (B == nullptr) return true;if (A == nullptr || A->val != B->val) return false;return myF(A->left, B->left) && myF(A->right, B->right);}bool isSubStructure(TreeNode *A, TreeNode *B) {if (A == nullptr || B == nullptr)return false;if (A->val == B->val)return myF(A, B);elsereturn isSubStructure(A->left, B) || isSubStructure(A->right, B);
无语，终于，推倒按照思路重新来，并学了下各个解析写的，设定一个标记变量res以后重新开始，这次终于对了。
bool myF2(TreeNode *A, TreeNode *B) {if (B == nullptr)return true;if (A == nullptr)return false;if (A->val != B->val)return false;return myF2(A->left, B->left) && myF2(A->right, B->right);}bool isSubStructure2(TreeNode *A, TreeNode *B) {bool res = false;if (A != nullptr && B != nullptr) {if (A->val == B->val)res = myF2(A, B);if (!res)res = isSubStructure(A->left, B);if (!res)res = isSubStructure(A->right, B);}return res;
3. 二叉树的镜像
晚饭后，继续。第九题：二叉树的镜像。这题简单，设置一个temp，递归！
TreeNode* mirrorTree(TreeNode* root) {if (root == nullptr)return nullptr;TreeNode* temp = root->left;root->left = mirrorTree(root->right);root->right = mirrorTree(tmp);return root;}
4. 对称的二叉树
第十题：对称的二叉树。判断一棵树是不是对称二叉树。判断就是三点：节点值是否相等，节点左值是否等于节点右值，右值是否等于左值。用递归。很简单一个题，却费力很久，一个初始条件判断错误，导致提交后系统提示使用了空指针。还需多多练习
bool myF(TreeNode *A, TreeNode *B) {if (A == nullptr && B != nullptr)return false;if (A != nullptr && B == nullptr)return false;if (A == nullptr && B == nullptr)return true;if (A->val != B->val)return false;return (myF(A->left, B->right) && myF(A->right, B->left));}bool isSymmetric(TreeNode *root) {if (root == nullptr)return true;return myF(root->right, root->left);
5. 从上到下打印二叉树
继续，第十一题：从上到下打印二叉树。这题数据结构基础题，用一个队列。很轻松，但中间有一个小失误，while判断反了，还是要心细。
vector<int> levelOrder(TreeNode *root) {queue<TreeNode *> queue;vector<int>vector(0);if (root== nullptr)return vector;queue.push(root);while (!queue.empty()){TreeNode* node=queue.front();queue.pop();vector.push_back(node->val);if (node->left!= nullptr)queue.push(node->left);if (node->right!= nullptr)queue.push(node->right);}return vector;}
6. 从上到下打印二叉树2.0
继续，第十二题：从上到下打印二叉树2.0。这个比较难，按层打印。尝试了一早上，没做出来。看了解析，发现一个很好理解的方法，自己尝试但是没有实现，这个解析做出来了，用一个nextLevel变量和一个remaining变量来记录每一层的信息。看懂以后自己很快敲出来。
vector<vector<int>> levelOrder(TreeNode *root) {queue<TreeNode *> queue;vector<vector<int>> vec;if (root == nullptr)return vec;queue.push(root);int nextLevel = 0;int remaining = 1;vector<int> temp;while (!queue.empty()) {TreeNode *node = queue.front();temp.push_back(node->val);queue.pop();remaining--;if (node->left) {queue.push(node->left);nextLevel++;}if (node->right) {queue.push(node->right);nextLevel++;}if (remaining == 0) {vec.push_back(temp);temp.clear();remaining = nextLevel;nextLevel = 0;}}return vec;}
7. 从上到下打印二叉树3.0
有点感觉，继续下一道！第十三题：从上到下打印二叉树3.0。这个也是按层打印，但是是蛇形打印。想设置一个bool的tag，循环true和false进行蛇形输出，第一次失败，情况是这样：
第二次也失败，看来这条路不通。
看了解析，发现不是路不通，方法可用，问题在于应该使用双端队列deque！百度deque用法后继续尝试。
vector<vector<int>> levelOrder(TreeNode *root) {if (!root)return {};vector<vector<int> > res;vector<int> temp;deque<TreeNode *> store; // 使用 dequestore.push_back(root);TreeNode *curr;bool tag = true;int remaining = 1, nextLevel = 0;while (!store.empty()) {if (tag) // 奇数层{curr = store.front();temp.push_back(curr->val);store.pop_front(); // 弹出顶部元素remaining--;if (curr->left) {store.push_back(curr->left); //从左往右向底部添加下一层nextLevel++;}if (curr->right) {store.push_back(curr->right); //从左往右向底部添加下一层nextLevel++;}} else // 偶数层{curr = store.back();temp.push_back(curr->val);store.pop_back(); // 弹出底部元素remaining--;if (curr->right) {store.push_front(curr->right); //从右往左向顶部添加nextLevel++;}if (curr->left) {store.push_front(curr->left); //从右往左向顶部添加nextLevel++;}}if (remaining == 0) {res.push_back(temp);temp.clear();remaining = nextLevel;nextLevel = 0;tag = !tag;}}return res;}
8. 二叉树中和为某一值的路径
应该是用深度优先算。上递归和回溯。试了一下，做不出来。翻看解析，其实和自己的思路差不多，自己没有将递归结束的条件写清楚。而且注意，如果遍历到一条路径的叶节点了，然后需要切换到下一条路径的叶节点（比如题目示例中，我们遍历完了 5-4-11-7，现在要从 7 切换到 右边的 2），我们需要先从 temp 中把 7 pop_back。这样才能保证切换了之后，temp里的值会是：5，4，11，2；而不是：5，4，11，7，2。
class Solution {private:vector<vector<int> > res;vector<int> temp;public:vector<vector<int>> pathSum(TreeNode *root, int sum) {if (root == nullptr)return {};preorder(root, sum);return res;}void preorder(TreeNode *root, int sum) {if (root == nullptr)return;temp.push_back(root->val);sum = sum - root->val;if (sum == 0)res.push_back(temp);preorder(root->left, sum); // 左preorder(root->right, sum); // 右temp.pop_back(); // 函数退出之前先弹出当前节点}}
9. 字符串的排列
今天再接再厉，争取再啃下一题，第十五题：字符串的排列。这题出在这里，是要用到树和递归，但是考虑到会给出重复的字符，这样可以用减枝法来优化试试。失败了，发现自己枚举到时候没法写出来。看了好多解析，有一种自己还是比较认可的。用回溯和无序的set来做：将字符串分为两部分，第一部分为第一个字符，第二部分为后面所有字符。求整个字符串的全排列，可以看成两步，第一步求所有可能出现在第一个位置的字符，即把第一个字符和后面所有字符交换。第二步，固定第一个字符，求后面所有字符排列。比如字符串“abc”，第一部分为字符a，第二部分为“bc”，首先a在第一个字符，求字符串“bc”的所有全排列得到：abc和acb。然后交换a和b，b放在第一个字符，求”ac”所有全排列得到：bac和bca。还原a和b后再交换a和c，c放在第一个字符，求“ba”所有全排列得到：cba和cab。用了好久才理解，前面凭空想是完全处理不来递归和回溯的过程，必须在纸上以树状图画出来。而且对于重复元素的减枝法的处理也是点睛之笔。
class Solution {public:vector<string> permutation(string s) {if (s.empty())return {};dfs(s, 0);return res;}private:vector<string> res;void dfs(string s, int x) {if(x == s.size() - 1) {res.push_back(s); // 加入res中return;}set<int> st;for(int i = x; i < s.size(); i++) {if(st.find(s[i]) != st.end())continue; // 重复st.insert(s[i]);swap(s[i], s[x]); // 交换，将 s[i] 固定在第 x 位dfs(s, x + 1); // 开启第 x + 1 位字符swap(s[i], s[x]); // 恢复交换}}};
10. 二叉搜素树的第k大节点
第十六题：二叉搜索树的第 k 大节点。而二叉搜索树的中序遍历为递增序列。按照右根左即可从大到小遍历，然后设置i记录第k大，二者相等即是答案。
class Solution {public:int kthLargest(TreeNode *root, int k) {myF(root, k);return res;}private:int res, i;void myF(TreeNode *root, int k) {if (root == nullptr)return;myF(root->right, k);//右++i;//计数if (i == k)//相等，把节点值保存并推出循环{res = root->val;return;}myF(root->left, k); //左}};
若有收获，就点个赞吧
0 人点赞
