vlambda博客
学习文章列表

【每日编程-445期】Leetcode.700. 二叉搜索树中的搜索



700. 二叉搜索树中的搜索




给定二叉搜索树(BST)的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在,则返回 NULL。

输入样例:

给定二叉搜索树:

4
/ \
2 7
/ \
1 3

和值: 2

输出样例:

      2
/ \
1 3
在上述示例中,如果要找的值是  5 ,但因为没有节点值为  5 ,我们应该返回  NULL

解决方法:

(1)算法的基本思想:

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树

递归遍历即可。

递归模板:

①处理root节点

②递归处理左子树

③递归处理右子树

(2)代码实现:

  
    
    
  
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

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

    }
};

明日预告:Leetcode.1025.除数博弈

爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。


最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:


选出任一 x,满足 0 < x < N 且 N % x == 0 。

用 N - x 替换黑板上的数字 N 。

如果玩家无法执行这些操作,就会输掉游戏。


只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两个玩家都以最佳状态参与游戏。


来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/divisor-game

样例一:

输入:2
输出:true
解释:爱丽丝选择 1,鲍勃无法进行操作。

样例二:

输入:3
输出:false
解释:爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。

提示:

  1. 1 <= N <= 1000

class Solution {
public:
    bool divisorGame(int N) {

    }
};