題目：51. 二叉搜索樹的第k個(gè)結(jié)點(diǎn)

知識(shí)點(diǎn)：二叉搜索樹

題目描述：

給定一棵二叉搜索樹，請(qǐng)找出其中的第k小的結(jié)點(diǎn)。例如， （5，3，7，2，4，6，8）? ? 中，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4。

解題思路：

解法一和解法二的思路是一樣的，即利用二叉搜索樹中序遍歷的結(jié)果為升序數(shù)列，只需通過(guò)中序遍歷，同時(shí)對(duì)結(jié)點(diǎn)進(jìn)行計(jì)數(shù)就可以了。

代碼：

//解法一（自研）：TreeNode* KthNode(TreeNode* pRoot, int k){if(pRoot == nullptr || k == 0)return nullptr;return FindKthNode(pRoot, k);}TreeNode* FindKthNode(TreeNode* pRoot, int& k){if(pRoot->left != nullptr){TreeNode* left = FindKthNode(pRoot->left, k);if(left != nullptr)return left;}if(--k == 0) return pRoot;if(pRoot->right != nullptr){TreeNode* right = FindKthNode(pRoot->right, k);if(right != nullptr)return right;}return nullptr;}//解法二（劍指Offer）： const BinaryTreeNode* KthNode(const BinaryTreeNode* pRoot, unsigned int k) {if(pRoot == nullptr || k == 0)return nullptr;return KthNodeCore(pRoot, k); }const BinaryTreeNode* KthNodeCore(const BinaryTreeNode* pRoot, unsigned int& k) {const BinaryTreeNode* target = nullptr;if(pRoot->m_pLeft != nullptr)target = KthNodeCore(pRoot->m_pLeft, k);if(target == nullptr){if(k == 1)target = pRoot;k--;}if(target == nullptr && pRoot->m_pRight != nullptr)target = KthNodeCore(pRoot->m_pRight, k);return target; }

?

總結(jié)

以上是生活随笔為你收集整理的《剑指Offer》51. 二叉搜索树的第k个结点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。