2023-1-10

454.4Sum II

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:


Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:


Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

python
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        '''
        用字典哈希表，存储前两个数组的两两之和的个数
        再循环后两个数组，如果两两之和的相反数在字典中
        count加相反数在字典中的值，返回count
        '''
        record, count = {}, 0
        for i in nums1:
            for j in nums2:
                if i+j in record:
                    record[i+j] +=1
                else:
                    record[i+j] =1
        for k in nums3:
            for l in nums4:
                if -(k+l) in record:
                    count += record[-(k+l)]
        return count

        
        # record = {}
        # for i in nums1:
        #     for j in nums2:
        #         if i+j in record:
        #             record[i+j] += 1
        #         else:
        #             record[i+j] = 1
        # count = 0
        # for x in nums3:
        #     for y in nums4:
                
        #         if -(x+y) in record:
        #             count += record[-(x+y)]
        # return count

203.Remove Linked List Elements


Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:


Input: head = [], val = 1
Output: []

Example 3:


Input: head = [7,7,7,7], val = 7
Output: []

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        '''
        用当前节点和虚拟节点初始化链表
        循环当前节点不为空
        如果当前节点的指针指向的值等于目标值
        当前节点的指针指向下下个
        否则当前节点向前移动一位
        返回虚拟节点的指针
        '''
        dummy=cur=ListNode(next=head)
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next
        
        
        # dummyNode = ListNode(next=head)
        # cur = dummyNode
        # while cur.next != None:
        #     if cur.next.val == val:
        #         cur.next = cur.next.next
        #     else:
        #         cur = cur.next
        # return dummyNode.next

169.Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:


Input: nums = [3,2,3]
Output: 3

Example 2:


Input: nums = [2,2,1,1,1,2,2]
Output: 2

python
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

66.Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:


Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:


Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:


Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

python
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        '''
        先转换成字符串再转换成int相加，返回int列表生成式
        '''
        return [int(i) for i in str(int(''.join(str(i) for i in digits)) + 1)]       
    	# join中跟可迭代对象，字符串str，列表list等，不能传int

374.Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

-1: Your guess is higher than the number I picked (i.e. num > pick).
1: Your guess is lower than the number I picked (i.e. num < pick).
0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

Example 1:


Input: n = 10, pick = 6
Output: 6

Example 2:


Input: n = 1, pick = 1
Output: 1

Example 3:


Input: n = 2, pick = 1
Output: 1

python
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n        
        while left <= right:
            mid = (left+right) // 2
            if guess(mid) == -1:
                right = mid -1
            elif guess(mid) == 1:
                left = mid +1
            elif guess(mid) == 0:
                return mid
            else:
                return 0
        return 0

2023-1-11

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:


Input: s = "()"
Output: true

Example 2:


Input: s = "()[]{}"
Output: true

Example 3:


Input: s = "(]"
Output: false

python
def maxSubArray(nums: List[int]) -> int:
        total=cur=nums[0]
        for i in nums[1:]:
            cur = max(cur+i, i)
            total = max(cur, total)
        return total

20.Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:


Input: s = "()"
Output: true

Example 2:


Input: s = "()[]{}"
Output: true

Example 3:


Input: s = "(]"
Output: false

python
class Solution:
    def isValid(self, s: str) -> bool:
        # record = []
        # for i in s:
        #     if i == '(':
        #         record.append(1)
        #     elif i == '[':
        #         record.append(2)
        #     elif i == '{':
        #         record.append(3)
        #     elif i == ')' and 1 in record:
        #         record.remove(1)
        #     elif i == ']' and 2 in record:
        #         record.remove(2)
        #     elif i == '}' and 3 in record:
        #         record.remove(3)
        # return len(record) ==0
        stack, record = [], {')':'(', ']':'[', '}':'{'}
        for i in s:
            if i in record.values():
                stack.append(i)
            else:
                if stack == [] or stack.pop() != record[i]:
                    return False
        return len(stack) == 0

141.Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:


Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:


Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:


Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        '''
        循环当前节点不为None，
        如果当前节点的值不为空，赋值空给当前节点
        反之返回真
        当前节点向后移动一位
        循环完毕返回假
        '''
        while head:
            if head.val is not None:
                head.val = None
            else:
                return True
            head = head.next
        return False
    
    
    	slow=fast=head
        while fast and fast.next:
			fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False Intersection of Two Linked Lists

160.Intersection of Two Linked Lists

Example 1:


Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:


Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:


Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        '''
        求出两链表长度，求出长度差值，
        移动较长的链表指针到较短链表的末尾
        比较两个指针是否指向同一个值，返回指针值，否则同时向前移动一位
        '''
        pA, pB = headA, headB
        while pA != pB:
            pA = headB if pA is None else pA.next
            pB = headA if pB is None else pB.next
        return pA



        # one = headA
        # two = headB
        # while one != two:
        #     one = headB if one is None else one.next
        #     two = headA if two is None else two.next
        # return one

704.Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:


Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:


Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left+right) //2
            if nums[mid] > target:
                right = mid-1
            elif nums[mid] < target:
                left = mid +1
            else:
                return mid
        return -1


        # left, right = 0, len(nums)-1
        # while left <= right:
        #     mid = (left+right) // 2
        #     if nums[mid] > target:
        #         right = mid - 1
        #     elif nums[mid] < target:
        #         left = mid + 1
        #     else:
        #         return mid
        # else:
        #     return -1

2023-1-12

94.Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:


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

Example 2:


Input: root = []
Output: []

Example 3:


Input: root = [1]
Output: [1]

python
# 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
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        def inorder(node):
            if node == None:
                return 
            if node.left != None:
                inorder(node.left)
            result.append(node.val)
            if node.right != None:
                inorder(node.right)
        inorder(root)
        return result
        '''
        用栈表示结果，定义中序遍历函数，如果当前树节点不为空，
        访问左子节点，添加当前节点值入栈，当前节点右子节点，
        返回栈
        递归执行顺序:https://www.bilibili.com/video/BV1Mr4y1C7VZ
        '''
        stack = []
        def inorder(root):
            if root:
                inorder(root.left)
                stack.append(root.val)
                inorder(root.right)
        inorder(root)
        return stack

144.Binary Tree Preorder Traversal

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example 1:


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

Example 2:


Input: root = []
Output: []

Example 3:


Input: root = [1]
Output: [1]

python
# 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
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        def preorder(root):
            if root:
                stack.append(root.val)
                preorder(root.left)
                preorder(root.right)
        preorder(root)
        return stack

110.Balanced Binary Tree

Given a binary tree, determine if it is

height-balanced

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:


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

Example 3:


Input: root = []
Output: true

python
# 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
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def depth(root):
            if not root:return 0
            if (left := depth(root.left)) ==-1:return -1
            if (right := depth(root.right)) ==-1:return -1
            if abs(left-right) > 1:return -1
            return max(left, right)+1        
        return depth(root) != -1

104.Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:


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

python
# 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
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def depth(root):
            if not root:return 0
            left = depth(root.left)
            right = depth(root.right)
            return max(left, right)+1
        return depth(root)

101.Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

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

python
# 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
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def compare(left, right):
            if left == None and right != None: return False
            elif left != None and right == None: return False
            elif left == None and right == None: return True
            elif left.val != right.val: return False
            outer = compare(left.left, right.right)
            inner = compare(left.right, right.left)
            isSame = outer and inner
            return bool(isSame)
        return compare(root.left, root.right)

543.Diameter of Binary Tree

求直径就是左右节点最大深度（用前序遍历（中左右）相加

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

上图：1的左节点2最大深度为2，1的右节点3最大深度1，该二叉树直径为2+1=3


Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:


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

python
# 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
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 求直径就是左右节点最大深度（用前序遍历（中左右）相加
        diameter = 0
        def dfs(root):
            nonlocal diameter
            if not root:return 0
            left = dfs(root.left)
            right = dfs(root.right)
            diameter = max(diameter, left+right)
            return max(left, right)+1
        dfs(root)
        return diameter

2023-1-13

226.Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Example 1:


Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:


Input: root = [2,1,3]
Output: [2,3,1]

Example 3:


Input: root = []
Output: []

python
# 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
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root):
            if not root:return
            root.left, root.right = root.right, root.left
            left = dfs(root.left)
            right = dfs(root.right)
            return root
        return  dfs(root)

111.Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:


Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

python
# 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
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        '''
        定义深度优先递归函数，入参root，
        返回左子节点和右子节点深度最小的加上根节点深度1，
        前序遍历左子节点和右子节点，
        如果左子节点深度为0，返回右子节点+1，
        如果右子节点深度为0，返回左子节点+1，
        如果都不为0，返回其中最小的+1
        '''
        def dfs(root):
            if not root:return 0
            left = dfs(root.left)
            right = dfs(root.right)
            if left == 0:return right+1
            elif right == 0:return left+1
            else:return min(left, right)+1
        return dfs(root)

257.Binary Tree Paths

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:


Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:


Input: root = [1]
Output: ["1"]

python
# 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
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        '''
        如果空节点，返回空路径，
        如果左右子节点都为空，返回根节点值的路径，
        前序遍历中左右，将左右路径相加即左节点右节点的路径
        返回列表生成式格式化成->相连
        '''
        def dfs(root):
            if not root:return []
            if not root.left and not root.right:
                return [str(root.val)]
            left = dfs(root.left)
            right = dfs(root.right)
            allpath = left + right
            return ['%s->%s' %(root.val, i) for i in allpath]
        return dfs(root)

108.Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a

*height-balanced*

binary search tree.

Example 1:


Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:


Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

python
# 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
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:return None
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

617.Merge Two Binary Trees

Example 1:


Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:


Input: root1 = [1], root2 = [1,2]
Output: [2,2]

python
# 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
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        '''
        确定递归函数参数和返回值(在root1上原地修改所以返回root1)，      确定终止条件（如果root1空，最终合并的树为root2，如果root2为空，为root1）
        确定单层递归逻辑单层套娃逻辑前序遍历（合并后的root1树左子节点为root1左子节点和root2左子节点之和，root1树右子节点为root1右子节点和root2右子节点之和）
        '''
        def dfs(root1, root2):
            if not root1:return root2
            if not root2:return root1
            root1.val += root2.val
            root1.left = dfs(root1.left, root2.left)
            root1.right = dfs(root1.right, root2.right)
            return root1
        return dfs(root1, root2)

2023-1-14

530.Minimum Absolute Difference in BST

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:


Input: root = [4,2,6,1,3]
Output: 1

Example 2:


Input: root = [1,0,48,null,null,12,49]
Output: 1

python
# 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
class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        result = []
        minimum = 10000 # minimum = float('inf')
        def dfs(root):
            if not root:return []
            dfs(root.left)
            result.append(root.val)
            dfs(root.right)
            return result
        dfs(root)
        for i in range(len(result)-1):
            minimum = min(result[i+1]-result[i], minimum)
            # 让minimum变量永远保持最小就是和一个无穷大的数比较，反之亦然
        return minimum

minimum = float('inf')正无穷

maximum= float('-inf')负无穷

2023-1-15

235.Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:


Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:


Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:


Input: root = [2,1], p = 2, q = 1
Output: 2

python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(root, p, q):
            if root.val > p.val and root.val > q.val:
                return dfs(root.left, p, q)
            if root.val < p.val and root.val < q.val:
                return dfs(root.right, p, q)
            return root
        return dfs(root, p, q)

二叉搜索数的左子树的节点值都比根节点值小，右子树的节点值都比根节点大

700.Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:


Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:


Input: root = [4,2,7,1,3], val = 5
Output: []

python
# 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
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        def dfs(root, val):
            if not root or root.val == val:return root
            if root.val > val:return dfs(root.left, val)
            if root.val < val:return dfs(root.right, val)
            return root
        return dfs(root, val)

2023-1-17

637. Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

Example 1:


Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].

Example 2:


Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]

python
# 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
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        info = []
        def dfs(root, depth=0):
            if root:
               if len(info) <= depth:
                   info.append([0, 0])
               info[depth][0] += root.val
               info[depth][1] += 1
               dfs(root.left, depth+1)
               dfs(root.right, depth+1)
        dfs(root)
        return [float(i /j) for i, j in info]

783.Minimum Distance Between BST Nodes

Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.

Example 1:


Input: root = [4,2,6,1,3]
Output: 1

Example 2:


Input: root = [1,0,48,null,null,12,49]
Output: 1

python
# 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
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def dfs(root, res):
            if root:
                dfs(root.left, res)
                res.append(root.val)
                dfs(root.right, res)
        res = []
        dfs(root, res)
        return min(res[i+1] - res[i] for i in range(len(res)-1))

目录

2023-1-10

454.4Sum II

203.Remove Linked List Elements

169.Majority Element

66.Plus One

374.Guess Number Higher or Lower

2023-1-11

20.Valid Parentheses

141.Linked List Cycle

160.Intersection of Two Linked Lists

704.Binary Search

2023-1-12

94.Binary Tree Inorder Traversal

144.Binary Tree Preorder Traversal

110.Balanced Binary Tree

104.Maximum Depth of Binary Tree

101.Symmetric Tree

543.Diameter of Binary Tree

2023-1-13

226.Invert Binary Tree

111.Minimum Depth of Binary Tree

257.Binary Tree Paths

108.Convert Sorted Array to Binary Search Tree

617.Merge Two Binary Trees

2023-1-14

530.Minimum Absolute Difference in BST

2023-1-15

235.Lowest Common Ancestor of a Binary Search Tree

700.Search in a Binary Search Tree

2023-1-17

637. Average of Levels in Binary Tree

783.Minimum Distance Between BST Nodes