Kth Smallest Element in a BST

原題鏈接Kth Smallest Element in a BST

給頂一個二叉搜索樹的根節點，找到這棵數第k小的值

兩種方法

• 遞歸法的中序遍歷
• 迭代法的中序遍歷

遞歸法，常規的中序遍歷

代碼如下

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int kthSmallest(TreeNode* root, int k) {int res = 0;inOrder(root, k, res);return res;} private:void inOrder(TreeNode* root, int& k, int& res){if(!root || !k) return;inOrder(root->left, k, res);//找到k個數即可if(--k == 0)res = root->val;inOrder(root->right, k, res);} };

迭代法，用棧實現

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode*> s;pushAllLeft(root, s);TreeNode* top = nullptr;while(k--){top = s.top();s.pop();//每彈出一個節點就將該節點的右子樹的左邊一列入棧pushAllLeft(top->right, s);}return top->val;} private:void pushAllLeft(TreeNode*root, stack<TreeNode*>& s){while(root){s.push(root);root = root->left;}} };

本題主要考察中序遍歷，除了遞歸法最好可以熟悉迭代法的求解

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----寻找二叉搜索树中第k小的元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。