Leetcode basic programming: Search

360. Two points search
     difficulty ： Simple
     Collection
     Given a n The elements are ordered （ Ascending ） integer array nums And a target value target , Write a function search nums Medium target, If the target value has a return subscript , Otherwise return to -1.

Example 1:

Input : nums = [-1,0,3,5,9,12], target = 9
Output : 4
explain : 9 Appear in the nums And the subscript is 4
Example 2:

Input : nums = [-1,0,3,5,9,12], target = 2
Output : -1
explain : 2 non-existent nums So back to -1

Tips ：

You can assume nums All elements in are not repeated .
n Will be in [1, 10000] Between .
nums Each element of will be in [-9999, 9999] Between .

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left=0
        right=nums.Length-1
        while left<=right:
            mid = (left+right)>>1
            if nums[mid] == target:
                return mid
                
            if nums[mid] < target:
                left = mid+1
            else:
                right = mid - 1
        return -1;

30. Search rotation sort array
    difficulty ： secondary
    Collection
    An array of integers nums In ascending order , The values in the array Different from each other .

Before passing it to a function ,nums In some unknown subscript k（0 <= k < nums.length） On the rotate , Make array [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（ Subscript from 0 Start Count ）. for example , [0,1,2,4,5,6,7] In subscript 3 It may turn into [4,5,6,7,0,1,2] .

Here you are. After rotation Array of nums And an integer target , If nums There is a target value in target , Returns its subscript , Otherwise return to -1 .

Example 1：

Input ：nums = [4,5,6,7,0,1,2], target = 0
Output ：4
Example 2：

Input ：nums = [4,5,6,7,0,1,2], target = 3
Output ：-1
Example 3：

Input ：nums = [1], target = 0
Output ：-1

Tips ：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums Each value in the unique
Topic data assurance nums Rotated on a previously unknown subscript
-10^4 <= target <= 10^4

Advanced ： You can design a time complexity of O(log n) Is there a better solution ？

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l=0
        r=len(nums)-1
        while l<r:
            mid = l+r+1>>1
            if nums[mid]>=nums[0]:
                l=mid
            else:
                r=mid-1
        
        if target >= nums[0]:
            l=0
        else:
            l=r+1
            r=len(nums)-1
        
        while l<r:
            mid=l+r>>1
            if nums[mid]>=target:
                r=mid
            else:
                l=mid+1
                
        if nums[r]==target:
            return r
        return -1

85. Symmetric binary tree
    difficulty ： Simple
    Collection
    Give you the root node of a binary tree root , Check whether it is axisymmetric .

Example 1：

Input ：root = [1,2,2,3,4,4,3]
Output ：true
Example 2：

Input ：root = [1,2,2,null,3,null,3]
Output ：false

Tips ：

The number of nodes in the tree is in the range [1, 1000] Inside
-100 <= Node.val <= 100

Advanced ： Can you use recursion and iteration to solve this problem ？

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def dfs(p:TreeNode, q:TreeNode):
    if not p or not q:
        return not p and not q
    return p.val==q.val and dfs(p.left,q.right) and dfs(p.right,q.left)
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return not root or dfs(root.left,root.right)

\78. Middle order traversal of binary trees

difficulty ： Simple

Collection

Given the root node of a binary tree root , Back to its Middle preface Traverse .

Example 1：

 Input ：root = [1,null,2,3]
 Output ：[1,3,2]

Example 2：

 Input ：root = []
 Output ：[]

Example 3：

 Input ：root = [1]
 Output ：[1]

Example 4：

 Input ：root = [1,2]
 Output ：[2,1]

Example 5：

 Input ：root = [1,null,2]
 Output ：[1,2]

Tips ：

• The number of nodes in the tree is in the range [0, 100] Inside
• -100 <= Node.val <= 100

Advanced : The recursive algorithm is very simple , Can you do it by iterative algorithm ？

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def dfs(root:TreeNode,ans):
    if not root:
        return
    dfs(root.left,ans)
    ans.append(root.val)
    dfs(root.right,ans)
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans=[]
        dfs(root,ans)
        return ans

\170. Binary search tree K Small elements

difficulty ： secondary

Collection

Given the root node of a binary search tree root , And an integer k , Please design an algorithm to find the k The smallest element （ from 1 Start counting ）.

Example 1：

 Input ：root = [3,1,4,null,2], k = 1
 Output ：1

Example 2：

 Input ：root = [5,3,6,2,4,null,null,1], k = 3
 Output ：3

Tips ：

• The number of nodes in the tree is n .
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

** Advanced ：** If the binary search tree is often modified （ Insert / Delete operation ） And you need to find the second one frequently k Small value , How will you optimize the algorithm ？

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    int k, ans;

    int kthSmallest(TreeNode* root, int _k) {
    
        k = _k;
        dfs(root);
        return ans;
    }

    bool dfs(TreeNode* root) {
    
        if (!root) return false;
        if (dfs(root->left)) return true;
        if ( -- k == 0) {
    
            ans = root->val;
            return true;
        }
        return dfs(root->right);
    }
};