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

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

给定

        4
       / \
      2   7
     / \
    1   3

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

      2     
     / \   
    1   3

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

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

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

递归

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

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;
        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;
        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