小赖子的英国生活和资讯

编程练习题: 二叉查找树BST

JustYY.com 小赖子的英国生活和资讯
阅读 桌面完整版

题意: 给定一个二分查找树 BST, Binary Search Tree, 查找指定的元素, 返回该节点开始的子树. 如果没找到就返回NULL.

给定

        4
       / \
      2   7
     / \
    1   3

如果我们要查找 2, 则返回子树: 

      2     
     / \   
    1   3

二叉树在C/C++中的定义

二叉树可以用结构体来定义, 其中左右子树都是递归的定义. 

1
2
3
4
5
6

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

递归

二叉查找树BST的最重要的特性就是左节点比根节点小, 而右节点比根子树大. 这样我们就可以每次根据根节点的大小, 相应的在左子树或者右子树中递归查找. 每次都摒弃一棵子树, 这样时间复杂度大约是 O(logn) , 如果遍历所有的节点则时间复杂度 O(n).

1
2
3
4
5
6
7
8

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        if (root->val == val) return root;
        return val > root->val ? searchBST(root->right, val) : searchBST(root->left, val);
    }
};
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        if (root->val == val) return root;
        return val > root->val ? searchBST(root->right, val) : searchBST(root->left, val);
    }
};

迭代

递归实现可以用迭代来实现, 自己操作堆栈, 每子把左子树或者右子树添加到堆栈中. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        stack<TreeNode*> st;
        st.push(root);
        while (st.size() > 0) {
            auto cur = st.top();
            st.pop();
            if (cur == nullptr) continue;
            if (val == cur->val) {
                return cur;
            }            
            if (val > cur->val) {
                st.push(cur->right);
            } else {
                st.push(cur->left);
            }
        }
        return NULL;
    }
};
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        stack<TreeNode*> st;
        st.push(root);
        while (st.size() > 0) {
            auto cur = st.top();
            st.pop();
            if (cur == nullptr) continue;
            if (val == cur->val) {
                return cur;
            }            
            if (val > cur->val) {
                st.push(cur->right);
            } else {
                st.push(cur->left);
            }
        }
        return NULL;
    }
};

由于这题和搜索的顺序关系不太大, 我们还可以用队列来实现, 按层来查找. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        deque<TreeNode*> Q;
        Q.push_back(root);
        while (Q.size() > 0) {
            auto cur = Q.front();
            Q.pop_front();
            if (cur == nullptr) continue;
            if (val == cur->val) {
                return cur;
            }            
            if (val > cur->val) {
                Q.push_back(cur->right);
            } else {
                Q.push_back(cur->left);
            }
        }
        return NULL;
    }
};
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        deque<TreeNode*> Q;
        Q.push_back(root);
        while (Q.size() > 0) {
            auto cur = Q.front();
            Q.pop_front();
            if (cur == nullptr) continue;
            if (val == cur->val) {
                return cur;
            }            
            if (val > cur->val) {
                Q.push_back(cur->right);
            } else {
                Q.push_back(cur->left);
            }
        }
        return NULL;
    }
};

英文: C/C++ Coding Exercise – Search in a Binary Search Tree

强烈推荐

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版

相关文章：

  1. Javascript 中 sleep 函数实现 阅读 桌面完整版 Javascript 中并没有 built-in 的 sleep 函数支持, 在 async/await/Promise 的支持之前, 我们可以用 busy-waiting 的方式来模拟: 1...
  2. 入佳能 6D Mark II 入门级全幅单反 阅读 桌面完整版 一直以来都想要全幅的单反, 在之前入了经典24-70mm F2.8佳能红圈镜头 (万能焦), 但是一直机身还是半画幅的 T3i, 朋友就说这红圈镜头需要在全幅单反上才能发挥最大的功效. 考虑许久, 咬咬牙, 入了佳能 6D Mark II...
  3. C++ 编程练习题 – 最多水容器 (递归) 阅读 桌面完整版 题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离. 上面的图的输入为 . 蓝色区域最可以装水为49. 最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度....
  4. C++ 编程练习题 – 找出第三大的数 阅读 桌面完整版 题意: 给出一个数组, 求第三大的数字是多少, 重复的数字并不算在内, 比如 第3大的数字是1 而不是 2. Using std::set set 是集合, 是有序的(从小到大),...
  5. 《Steem 指南》之 justyy 在线工具与 API 系列 – 同时给多个帐号发送SBD或者STEEM 阅读 桌面完整版 同时给多个帐号发送SBD或者STEEM STEEMIT 和 BUSY 的前端都有一个内置的钱包工具, 您可以一次给一个帐号发送 SBD 或者 STEEM. 当我们要给很多很多人发送钱的时候, 就显得有些不方便了. 这时候可以用这个在线工具: https://steemyy.com/wallet-tool/...
  6. 拔牙后的注意事项(图, 慎入) Care of Mouth after Extraction 阅读 桌面完整版 昨天又拔了两颗牙, 初步定在5月4号装牙套. 这是牙医诊所给的术后注意事项: 拔完后需要等3-4小时麻醉失效后才能吃喝. 稍微流点血是很正常的. 但是请不要漱口吐出, 因为这会加速流血. 你只要轻轻的含着口水并咽下即可. 如果一直流血, 请拿着纱布(并不是纸巾)放在拔牙处20分钟. 24小时内请不要运动, 术后几小时内回家静静坐着. 12小时内不要吸烟,...
  7. 试用 Linkedin (领英) 高级帐号 (Premium) 阅读 桌面完整版 Linkedin (领英) 算是比较靠谱的职业社交网站, 在上面有很多猎头, 很多知名公司的HR 无时无刻在招人. 特别领英在被微软收购之后, 名气就变得大了许多. 领英是免费使用的, 但也有付费用户, 有给猎头的, 也有给想找工作的. 价格并不便宜,...
  8. 英国中部的 主题公园 – Drayton Manor 阅读 桌面完整版 drayton-manor 在英国中部. 是一个小孩子玩的主题公园. 这次老大三岁生日就带他去了. 因为那里有他最喜欢的 Tomas 火车. 地址: Drayton Manor Drive Tamworth, Staffordshire...
Exit mobile version