题解 | #二叉搜索树的第k个节点#

第十二题 中序遍历 找指定位置的结点

建议先看第二种代码 递归实现的 代码比较简单左根右直接遍历

第一种方法 利用栈的非递归 

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    int KthNode(TreeNode* proot, int k) {
        // 主要思想中序遍历 遍历到第k个即可
        // 第二种 非递归
        if(proot==NULL)
            return -1;
        // write code here
        stack<TreeNode *>p;
        TreeNode* temp;
        p.push(proot);
        while(!p.empty())
        {
            // 有左孩子 就一直入栈
            while(p.top()->left!=NULL)
            {
                p.push(p.top()->left);
            }
            // 如果说 k正好为1，那就是当前栈顶
            if(k==1)
                return p.top()->val;
            // 如果说遍历超过了，就直接返回-1
            if(k<1)
                return -1;
            else{
                // 当前点>1 说明不是这个点 开始利用栈向上往回找父结点
                // 将父结点的右子树 存进去
                temp=p.top();
                p.pop();
                k--;
                // 判断有没有右子树 没有的话 就直接网上了
                while(temp->right == NULL)
                {
                    // 没有父结点了(当前的结点没有右子树，并且栈都空了 就说明 k太大 超过了要求 直接返回-1)
                    if(p.empty())
                        return -1;
                    // 在往回找父结点的时候 有可能 k就是了，就讲结果输出
                    // 比如说 12345全是左孩子的一根直线，那么假设k=2 就是在向上找父节点的时候 找到了4这个结点
                    if(k==1)
                        return p.top()->val;
                    
                    // 如果说 当前 k不为1 说明还要输出 p不为空 说明还有父节点 就继续向上寻找
                    // 并且 因为是中序遍历 所以往上找的时候，这一结点已经属于被访问过了，所以要删掉 并且k--
                    temp=p.top();
                    p.pop();
                    k--;
                }
                // 此时得到的temp有右结点 则入栈
                p.push(temp->right);
                
            }
        }
        return -1;
    }
};

// 第二种方法 递归实现 代码更简单 可以先看第二种

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    int KthNode(TreeNode* proot, int k) {
        // 边界问题 proot是空 或者k小于等于0
        if(proot == NULL || k<=0)
            return -1;
        
        // 中序遍历 找指定位置的结点
        // 利用递归 代码更简单 先中序遍历一遍 再找指定的第k个。
        // ans是一个数组 用来保存中序遍历的序列
        vector<int> ans;
        // 开始中序遍历
        zhongxv_bianli(proot,ans);
        
        // 你可以删掉下面遍历的注释 输出一遍ans
        /*
        for(int i = 0 ;i<ans.size();i++)
            cout<<ans[i]<<" ";
        cout<<endl;
        */
        
        // 如果说 遍历完了的结果都比k小 说明长度不够 返回-1
        if(ans.size() < k)
            return -1;
        // 最后 结果就是第k个 数组输出要-1
        return ans[k-1];
    }
    
    // 常规的递归的 中序遍历代码 加上了一个 将输出数据换成 保存val
    // ans是引用类型 可以随着中序遍历 一直push所需要的值
    void zhongxv_bianli(TreeNode* proot,vector<int> &ans){
        if(proot == NULL)
            return;
        else{
            zhongxv_bianli(proot->left,ans);
            ans.push_back(proot->val);
            zhongxv_bianli(proot->right,ans);
        }
    }
};