Algorithm Problem: Find Out the Minimum Number that Great or Equal to a Given Number In BST

By | 2013 年 1 月 1 日

Given a BST and a Number k, find out the minimum number p that p >= k.
给定一个BST的根,以及一个数k,返回在BST中的不小于k的最小的节点。

The method is descriped below, in the code.
具体方法在代码中注释得很清楚了.

The recursive and non-recursive code is included.
下面的代码中包含了递归和非递归两种.


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};
TreeNode *findKRecursive(TreeNode *root, int k) {
    if (NULL == root) {
        //there is no node that match the requisite.
        //在这颗空子树中是找不到目标的
        return NULL;
    }
    if (root->val == k) {
        //the node equal to k is find
        //找到了正好等于k的节点,这就是全局要找的节点。
        return root;
    } else if (root->val < k) {
        //root is less than k, so the result node is in it's right sub-tree, if there is.
        //如果根节点的值小于k,那么唯一的满足条件的节点只能去右子树中查找,如果右子树中没有,那整棵树也没有。
        return findKRecursive(root->right, k);
    } else {
        //root is > k, so the target node may be in it's left sub-tree, or is the current node.
        //如果根节点的值>k,那么值更小的满足要求的节点可能出现在左子树中
        TreeNode *knode = findKRecursive(root->left, k);
        if (knode) {
            //if a node is found in left sub-tree, then knode->value must <= cur->value, so return it
            //如果左子树中确实找到了一个节点满足要求,那么他的值一定不大于当前节点的值
            return knode;
        } else {
            //or there is no node which value is >= k, then , root is the best choice for the result.
            //否则左子树中没有>=k的节点,那最小的满足>=k要求的节点就是root了。
            return root;
        }
    }
}

TreeNode *findK(TreeNode *root, int k) {
    TreeNode *lastFound = NULL;//record the last node found which value is >= k
    TreeNode *cur = root;//current node to search for.
    while (cur) {
        if (cur->val == k) {
            //the node equal to k is find
            //找到了正好等于k的节点,这就是全局要找的节点。
            return cur;
        } else if (cur->val > k) {
            //root is > k, so the result may be in it's left sub-tree, or cur is the best result
            //如果根节点的值>k,那么值更小的满足要求的节点可能出现在左子树中,如果左子树没有的话,这就是最好的选择
            lastFound = cur;
            cur = cur->left;
        } else {
            //root is less than k, so the result node is in it's right sub-tree, if there is.
            //如果根节点的值小于k,那么唯一的满足条件的节点只能去右子树中查找,如果右子树中没有,那整棵树也没有。
            cur = cur->right;
        }
    }
    return lastFound;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注