给定一个二叉搜索树的根节点root和一个整数k请你设计一个算法查找其中第k小的元素k从 1 开始计数。示例 1输入root [3,1,4,null,2], k 1输出1示例 2输入root [5,3,6,2,4,null,null,1], k 3输出3提示树中的节点数为n。1 k n 1040 Node.val 104思路二叉搜索树有一个特点就是中序遍历的结果是有序的。可以使用中序遍历的方法遍历二叉搜索树然后返回第k小的元素。中序非递归遍历需要用栈来遍历1、将根节点和左子树的节点入栈stack.push(root);2、一直走向他的左子树循环入栈直到节点为空while(root){ rootroot-left; stack.push(root); }3、栈顶出栈走向右子树节点出栈第k次即为第k小的元素直接返回rootstack.top(); rootroot-right;4、第二次循环继续持续走root节点的左子树让左子树入栈while(root){ rootroot-left; stack.push(root); }5、栈为空和root为空时退出循环。由于题目的限制不需要考虑k不满足条件的情况。int kthSmallest(TreeNode* root, int k) { if(!root) return -3; stackTreeNode* stack; while(root||!stack.empty()){ //一直往左走 while(root){ stack.push(root); rootroot-left; } //root为空时出栈 if(!stack.empty()){ rootstack.top(); stack.pop(); k--; if(0k) return root-val; } rootroot-right; } return 0; }如果你需要频繁地查找第k小的值你将如何优化算法可以记录下以每个结点为根结点的子树的结点数并在查找第 k 小的值时使用如下方法搜索令 node 等于根结点开始搜索。对当前结点 node 进行如下操作【1】如果 node 的左子树的结点数 left 小于 k−1则第 k 小的元素一定在 node 的右子树中令 node 等于其的右子结点k 等于 k−left−1并继续搜索。【2】如果 node 的左子树的结点数 left 等于 k−1则第 k 小的元素即为 node 结束搜索并返回 node 即可。【3】如果 node 的左子树的结点数 left 大于 k−1则第 k 小的元素一定在 node 的左子树中令 node 等于其左子结点并继续搜索。class MyBst { public: MyBst(TreeNode *root) { this-root root; countNodeNum(root); } ​ // 返回二叉搜索树中第k小的元素 int kthSmallest(int k) { TreeNode *node root; while (node ! nullptr) { int left getNodeNum(node-left); if (left k - 1) { node node-right; k - left 1; } else if (left k - 1) { break; } else { node node-left; } } return node-val; } ​ private: TreeNode *root; unordered_mapTreeNode *, int nodeNum; ​ // 统计以node为根结点的子树的结点数 int countNodeNum(TreeNode * node) { if (node nullptr) { return 0; } nodeNum[node] 1 countNodeNum(node-left) countNodeNum(node-right); return nodeNum[node]; } ​ // 获取以node为根结点的子树的结点数 int getNodeNum(TreeNode * node) { if (node ! nullptr nodeNum.count(node)) { return nodeNum[node]; }else{ return 0; } } }; ​ class Solution { public: int kthSmallest(TreeNode* root, int k) { MyBst bst(root); return bst.kthSmallest(k); } };推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginx ZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习:链接