leetcode230 - Kth Smallest Element in a BST

题目:
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
这道题就是遍历BST,取出第k小的数。只需要取出中序遍历二叉树的第k个数据就行了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inOrder(TreeNode*& root, int &target, int &k){
        if(root != NULL and k > 0){
            inOrder(root->left, target, k);
            k--;
            if(k == 0){
                target = root ->val;
                return;
            }
            inOrder(root->right, target, k);
        }
        
    }
    int kthSmallest(TreeNode* root, int k) {
        int target = -1;
        inOrder(root, target, k);
        return target;
    }
};
上一篇:数据结构--2--stack, heap, queue, tree


下一篇:Android灯光系统通知灯【转】