leetcode 7.27-8.02

2020-08-02

面试题08.03 魔术索引
700 二叉搜索树中的搜索

面试题08.03. 魔术索引

魔术索引。在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例1:

输入：nums = [0, 2, 3, 4, 5]
输出：0
说明: 0下标的元素为0
示例2:

输入：nums = [1, 1, 1]
输出：1
说明:

nums长度在[1, 1000000]之间
此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/magic-index-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：扫一遍数组，判断$A[i]==i$，简单快捷，$O(n)$

方法二：如果这个数组是个单调递增数组，是可以直接用二分查找来做的。本题中允许数字重复，只能采用部分剪枝的方法，尽可能在靠左的子序列中找到答案。用递归，先找左半序列，找不到再找右半序列。

dclass Solution {
private:
    int findRecursive(vector<int>& nums, int left, int right) {
        if (left > right)
            return -1;
        int mid = (left + right) / 2
        int left_ret = findRecursive(nums, left, mid - 1);
        if (left_ret != -1)
            return left_ret;
        else if (nums[mid] == mid)
            return mid;
        elsen
            return findRecursive(nums, mid + 1, right);
    }
public:
    int findMagicIndex(vector<int>& nums) {
        return findRecursive(nums, 0, nums.size()-1);
    }
};

700. 二叉搜索树中的搜索

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

例如，

给定二叉搜索树:

和值: 2
你应该返回如下子树:

  2     
 / \   
1   3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：就简单的二叉搜索树查找，找到了直接返回那个节点就可以。

AC代码：

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        p = root
        while p != None:
            if p.val == val:
                return p
            elif p.val > val:
                p = p.left
            else:
                p = p.right
        return None