Open guanpengchn opened 6 years ago
给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: int index=0; TreeNode* Calc(TreeNode* root, int k){ if(root){ TreeNode* left = Calc(root->left, k); if(left){ return left; } index++; if(k==index){ return root; } TreeNode* right = Calc(root->right, k); if(right){ return right; } } return nullptr; } TreeNode* KthNode(TreeNode* pRoot, int k) { return Calc(pRoot, k); } };
题目描述
给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。