1、翻转单词序列

本题考点：子串划分，子串逆置 牛客链接

题目描述：

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

数据范围：1≤n≤100 
进阶：空间复杂度 O(n)  ，时间复杂度 O(n)  ，保证没有只包含空格的字符串

解题思路：

以空格作为分隔将子串进行划分进行逆置，然后在对子串整体进行逆置。

代码：

class Solution {
public:void Reverse(string& str, int begin, int end){while(begin < end){char temp = str[begin];str[begin] = str[end];str[end] = temp;begin++;end--; }}string ReverseSentence(string str) {if(str.empty())return "";int j = 0;int i = 0;int len = str.size();while(i < len){while(i < len && str[i] != ' ') i++;Reverse(str, j, i - 1);while(i < len && str[i] == ' ') i++;j = i;}Reverse(str, j, i - 1);Reverse(str, 0, str.size() - 1);return str;}
};

2、按之字形顺序打印二叉树

本题考点：树遍历，stack，queue结合使用

题目描述：

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0≤n≤1500,树上每个节点的val满足∣val∣<=1500
要求：空间复杂度：O(n)，时间复杂度：O(n)

解题思路：

代码：

class Solution {
public:vector<vector<int> > Print(TreeNode* pRoot) {vector<vector<int>> result;if(pRoot == nullptr)return result;stack<TreeNode* > st;queue<TreeNode* > qe;int dir = 1; / 1从左向右 2从右向左 （控制方向）st.push(pRoot);while(!st.empty()){vector<int> v;while(!st.empty()){TreeNode* cur = st.top();st.pop();v.push_back(cur->val);/控制左右子树顺序TreeNode* first = dir == 1 ? cur->left : cur->right;TreeNode* second = dir == 1 ? cur->right : cur->left;/入队列暂存if(first != nullptr)qe.push(first);if(second != nullptr)qe.push(second);}/移到栈中while(!qe.empty()){st.push(qe.front());qe.pop();}dir == 1 ? dir = 2 : dir = 1; /改变方向result.push_back(v);}return result;}};

3、二叉搜索树的第k个节点

本题考点：二叉搜索树的理解 牛客链接

题目描述：

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1.返回第k小的节点值即可

2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3.保证n个节点的值不一样

数据范围：0≤n≤1000，0≤k≤1000，树上每个结点的值满足0≤val≤1000
进阶：空间复杂度O(n)，时间复杂度 O(n)

解题思路：

1、方法一：递归中序遍历。

2、方法二：迭代借助栈来完成中序遍历。

方法一比较简单,这里说下方法二的解题思路。
(1)将左子树全部入栈,出栈的时候判断其右子树是否为空。若不为空则把右子树当做新的树来将其左子树也全部入栈。

(2)这里的判断条件确实不太容易想，正常容易想到的就是栈不为空，但并不是这样，如图。

 代码：

class Solution {
public:/方法一:void levelNode(TreeNode* proot, int& k, int& find){if(proot == nullptr || k <= 0)return;levelNode(proot->left, k, find);k--;if(k == 0){find = proot->val;return;}levelNode(proot->right, k, find);}int KthNode(TreeNode* proot, int k) {if(proot == nullptr)return -1;int find = -1;levelNode(proot, k, find);return find;}/方法二:int KthNode(TreeNode* proot, int k) {if(proot == nullptr)return -1;stack<TreeNode* > st;TreeNode* node = proot;do{while(node != nullptr){st.push(node);node = node->left;}if(!st.empty()){TreeNode* front = st.top();st.pop();k--;if(k == 0)return front->val;/右子树不为空,将其作为根节点继续入栈if(front->right)  node = front->right;}}while(node != nullptr ||  !st.empty());return -1;}
};