2 个跟二叉搜索树相关的题。

700. Search in a Binary Search Tree

Analysis

在二叉搜索树中，查找与给定值相同的结点，并返回这个结点。

Code

dfs

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root || root->val == val) return root;
        else if(root->val > val) return searchBST(root->left, val);
        else return searchBST(root->right, val);
    }
};

bfs

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root) return root;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if(node->val == val) return node;
            else if(node->val > val && node->left) q.push(node->left);
            else if(node->val < val && node->right) q.push(node->right);
        }
        return nullptr;
    }
};

loop

由于二叉搜索树具有左边小右边大性质，这个题还可以写的更直接：

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

实际上，这就是二分查找。

701. Insert into a Binary Search Tree

Analysis

这个题与上面的题基本一致，只是需要插入一个结点，实际上就是在查找插入的位置。

Code

dfs

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        if(root->val > val) root->left = insertIntoBST(root->left, val);
        else root->right = insertIntoBST(root->right, val);
        return root;
    }
};

bfs

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if(node->val > val) {
                if(node->left) q.push(node->left);
                else {
                    node->left = new TreeNode(val);
                    break;
                }
            } else {
                if(node->right) q.push(node->right);
                else {
                    node->right = new TreeNode(val);
                    break;
                }
            }
        }
        return root;
    }
};

loop

同样，根据二叉搜索树的性质，也可以直接用循环来做：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        TreeNode *tmp = root;
        while(root) {
            if(root->val > val) {
                if(root->left) root = root->left;
                else {
                    root->left = new TreeNode(val);
                    break;
                }
            } else {
                if(root->right) root = root->right;
                else {
                    root->right = new TreeNode(val);
                    break;
                }
            }
        }
        return tmp;
    }
};

Summary

这几天有关树的题都不难，所以尽量把能想到的方法都写出来。