翻转单词序列、按之字形顺序打印二叉树、二叉搜索树的第k个节点

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:
    vectorint> > Print(TreeNode* pRoot) {
        vectorint>> result;
        if(pRoot == nullptr)
            return result;
        
        stack st;
        queue 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 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;
    }
};