牛客网——二叉搜索树的第k个结点（C++）

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

C++

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    void dfs(TreeNode* pRoot, vector<TreeNode*>& tmp)
    {
        if(pRoot)
        {
            dfs(pRoot->left,tmp);
            tmp.push_back(pRoot);
            dfs(pRoot->right,tmp);
        }
    }
    
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        vector<TreeNode*> tmp;
        dfs(pRoot,tmp);
        int n=tmp.size();
        if(0==n || k<=0)
        {
            return NULL;
        }
        if(k<=n)
        {
            return tmp[k-1];
        }
        return NULL;
    }

    
};

最后

以上就是执着薯片最近收集整理的关于牛客网——二叉搜索树的第k个结点（C++）的全部内容，更多相关牛客网——二叉搜索树内容请搜索靠谱客的其他文章。