《剑指offer》二叉搜索树的第k个结点

题目链接：?rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述给定一颗二叉搜索树，请找出其中的第k大的结点。例如，， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。思路对于一颗二叉搜索树而言，我们要得到其排序的数列需要用到的是中序遍历，所以我们就在终须遍历的过程中来需找第k个遍历到的结点

/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};*/class Solution{public:TreeNode* KthNode(TreeNode* pRoot, unsigned int k){if(pRoot==nullptr || k==0)return nullptr;return KthNodeCore(pRoot,k);}TreeNode *KthNodeCore(TreeNode *root, unsigned int& k){TreeNode *target = nullptr;if(root->left!=nullptr)target = KthNodeCore(root->left,k);if(target==nullptr){if(k==1)target=root;k–;}if(target==nullptr && root->right!=nullptr)target = KthNodeCore(root->right,k);return target;}};

不愧是春城，花香四季，品种繁多。

相关文章：

你感兴趣的文章：

标签云：