# LeetCode Data Structure
## Array
### 217. Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
* **Approach**
1. sort the array first, if the back number equals to front number, return true
2. or use the set in python
```python
class Solution(object):
def containsDuplicate(self, nums):
# nums=sorted(nums)
# for i in range(1,len(nums)):
# if nums[i]==nums[i-1]:
# return True
# return False
#solution 2
return len(nums)!=len(set(nums))
```
### 53. Maximum Subarray
Given an integer array nums, find the
subarray which has the largest sum and return its sum.
```
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```
* **Approach**
1. linearly travel the list, and keep track of the current sum
2. if current sum<0 means that there is a negative number, and it is not helpful to us, so we reset the current sum.
3. Note: In the loop, we need to check if currSum is less than 0 first, i.e., [-2,1], first round currSum will be -2, then in the second round, we check it first and find out that the currSum is less than 0, this means we don't need the previous value
5. each round compare the current sum and the max sum to see if we need to update max sum
```python
class Solution(object):
def maxSubArray(self, nums):
maxSum = nums[0]
currSum = 0
for num in nums:
# if currSum < 0 means that there is a negative number
# so we reset the currSum since the negative number is not helpful to us
if currSum < 0:
currSum = 0
currSum += num
maxSum = max(maxSum, currSum)
return maxSum
```
### 1. Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
```
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
```
* **Approach**
use the map to store the difference between the nums[i] and the target
i.e. nums=[2,7,11,15]
nums[0]=2, not in map, so now map={7:0}, which means that the value of index 0 in nums need to plus 7 to get to the target
The next round nums[1]=7, which 7 is in the map, means the value of index 1 in nums can mathch with the value of index 0
```python
class Solution(object):
def twoSum(self, nums, target):
map={}
for i in range(len(nums)):
if nums[i] not in map:
map[target-nums[i]]=i
else:
return map[nums[i]],i
```
### 88. Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
```
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
```
* Solution
```python
class Solution(object):
def merge(self, nums1, m, nums2, n):
# compare the list reversely
# 大的就先放到nums1的後面
i, j = m-1, n-1
for right in range(m+n-1, -1, -1):
#nums2沒有資料，就直接輸出nums1即可
if j < 0:
break
#nums1 index的值大於nums2的，所以擺到nums1後面相對的位子
if i >= 0 and nums1[i] > nums2[j]:
nums1[right] = nums1[i]
i -= 1
else:
nums1[right] = nums2[j]
j -= 1
```
### 350. Intersection of Two Arrays II
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
```
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
```
* **Approach**
The map is used to store the appearing times of each value in the longer list, so if the value appear in the other list, corresponding map value will decrease 1
```python
class Solution(object):
def intersect(self, nums1, nums2):
result=[]
# case1:nums2 is longer
if len(nums1)<=len(nums2):
map={}
for i in range(len(nums2)):
if nums2[i] not in map:
map[nums2[i]] = 1
else:
map[nums2[i]] += 1
for i in range(len(nums1)):
if ((nums1[i] in map)and(map[nums1[i]]!=0)):
map[nums1[i]]-=1
result.append(nums1[i])
# case2:nums1 is longer
else:
map={}
for i in range(len(nums1)):
if nums1[i] not in map:
map[nums1[i]] = 1
else:
map[nums1[i]] += 1
for i in range(len(nums2)):
if ((nums2[i] in map)and(map[nums2[i]]!=0)):
map[nums2[i]]-=1
result.append(nums2[i])
return result
```
### 566. Reshape the Matrix
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.
You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.
The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
* [tutorial](https://www.youtube.com/watch?v=JCb27sANkC0)
```python
class Solution(object):
def matrixReshape(self, mat, r, c):
"""
:type mat: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
"""
row,col = len(mat),len(mat[0])
if row*col != r*c:
return mat
else:
#create a r*c matrix
result = [[0 for _ in range(c)] for _ in range(r)]
new_row = 0
new_col = 0
for i in range(row):
for j in range(col):
#row-major
result[new_row][new_col] = mat[i][j]
#if the column comes to the end, means we need to go to the next row and reset the column
new_col += 1
if new_col == c:
new_row += 1
new_col = 0
return result
```
### 118. Pascal's Triangle
Given an integer numRows, return the first numRows of Pascal's triangle.
```
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
```
```python
class Solution(object):
def generate(self, numRows):
if numRows == 1:
pascal = [[1]]
elif numRows == 2:
pascal = [[1],[1,1]]
else:
pascal = [[1],[1,1]]
for i in range(2,numRows):
layer=[]
for idx in range(i+1):
if idx==0 or idx==i:
layer.append(1)
else:
layer.append(pascal[i-1][idx-1] + pascal[i-1][idx])
pascal.append(layer)
return pascal
```
### 36. Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
1. A Sudoku board (partially filled) could be valid but is not necessarily solvable.
2. Only the filled cells need to be validated according to the mentioned rules.
**Approach**
1. Use hashset to store the value in each row, col, and squares
2. defaultdict: https://ithelp.ithome.com.tw/articles/10193094
3. The way to check the 3*3 squares is to use // (integer division)
```python
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = collections.defaultdict(set)
cols = collections.defaultdict(set)
squares = collections.defaultdict(set)
for r in range(9):
for c in range(9):
if board[r][c] == ".":
continue
if (board[r][c] in rows[r] or
board[r][c] in cols[c] or
board[r][c] in squares[(r//3, c//3)]):
return False
rows[r].add(board[r][c])
cols[c].add(board[r][c])
squares[(r//3, c//3)].add(board[r][c])
return True
```
### 74. Search a 2D Matrix
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
**Approach**
1. Use two binary search
2. First search the correct row, we can compare the right most value or the left most value to move our pointers
3. After finding the correct row, use binary search to search the target in that row
```python
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
Rows, Cols = len(matrix), len(matrix[0])
top, bottom = 0, Rows-1
left, right = 0, Cols-1
while top <= bottom:
row = (top + bottom) // 2
if target > matrix[row][-1]:
top = row + 1
elif target < matrix[row][0]:
bottom = row - 1
else:
break
if not (top <= bottom):
return False
row = (top + bottom) // 2
while left <= right:
col = (left + right) // 2
if target == matrix[row][col]:
return True
elif target > matrix[row][col]:
left = col + 1
else:
right = col - 1
return False
```
## String
### 387. First Unique Character in a String
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
```
Input: s = "leetcode"
Output: 0
```
**Approach**
Use counter to count the appearing time of each character, then find the first character that just appear once
```python
class Solution:
def firstUniqChar(self, s: str) -> int:
num = Counter(s)
for i in range(len(s)):
if num[s[i]] == 1:
return i
return -1
```
### 383. Ransom Note
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
```
Input: ransomNote = "aa", magazine = "aab"
Output: true
```
```python
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
if len(ransomNote) > len(magazine):
return False
ran, mag = Counter(ransomNote), Counter(magazine)
for char in range(len(ransomNote)):
if ransomNote[char] not in mag:
return False
elif ran[ransomNote[char]] > mag[ransomNote[char]]:
return False
return True
```
### 242. Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
```python
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
sCount, tCount = Counter(s), Counter(t)
return True if sCount == tCount else False
```
## Linked list
### 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.
```
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).
```
```python
class Solution(object):
def hasCycle(self, head):
if not head:
return False
else:
normal=head
fast=head
while fast and fast.next and fast.next.next:
normal = normal.next
fast = fast.next.next
if normal == fast:
return True
return False
```
### 21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
```python
class Solution(object):
def mergeTwoLists(self, list1, list2):
if ((not list1) and (not list2)): #both lists are empty
return list1
elif not list1 : #one of the list is empty
return list2
elif not list2:
return list1
else:
result=current=ListNode() #current is the pointer for the result linked list
while list1 and list2:
if list1.val < list2.val:
current.next = list1
current = list1 #update current pointer
list1 = list1.next #compare the next value
else:
current.next = list2
current = list2
list2 = list2.next
if list1:
current.next = list1
else:
current.next = list2
return result.next
```
### 203. Remove Linked List Elements
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
```
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
```
**Approach**
There are 3 situations, and we use two pointers prev and curr:
1. The current node.val is not equal to val, we can simply just move our prev and curr pointers, and the prev pointer is used to point the previous node of curr pointer
2. The current node is equal to val, but is at the first position, so we just move the head and curr pointer to the next node
3. The current node is equal to val and is not at the first position, so we let the prev.next = curr.next in order to jump through our val node
```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]:
if not head:
return head
curr = head
prev = None
while curr:
if curr.val != val:
prev = curr
curr = curr.next
else:
if curr == head:
head = head.next
curr = curr.next
else:
prev.next = curr.next
curr = curr.next
return head
```
### 206. Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
```python
class Solution(object):
def reverseList(self, head):
if not head:
return head
else:
prev = None
curr = None
while head:
curr = head
head = head.next
curr.next = prev
prev = curr
return curr
```
### 83. Remove Duplicates from Sorted List
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
```
Input: head = [1,1,2,3,3]
Output: [1,2,3]
```
**Approach**
1. Use set to store the elements, and use two pointers prev and curr
2. If the val appears first time, add it to the set and move the pointers
3. If the val already appears, we can use prev.next = curr.next to jump through the node
```python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
curr, prev = head, None
num = set()
while curr:
if curr.val not in num:
num.add(curr.val)
prev = curr
curr = curr.next
else:
prev.next = curr.next
curr = curr.next
return head
```
## Stack/Queue
### 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.
```
Input: s = "()[]{}"
Output: true
```
**Approach**
Since the open brackets must be closed by the same type of brackets, so if we meet close bracket, we can check if the top of the stack is the corresponding open bracket
```python
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for i in range(len(s)):
if (s[i] == "(" or s[i] == "[" or s[i] == "{"):
stack.append(s[i])
else:
if not stack:
return False
elif s[i] == ")":
tmp = stack.pop()
if tmp != "(": return False
elif s[i] == "]":
tmp = stack.pop()
if tmp != "[": return False
elif s[i] == "}":
tmp = stack.pop()
if tmp != "{": return False
return True if not stack else False
```
### 232. Implement Queue using Stacks
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.
Notes:
You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
```
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
```
```python
class MyQueue:
def __init__(self):
self.stack1, self.stack2 = [], []
def push(self, x: int) -> None:
self.stack1.append(x)
def pop(self) -> int:
if self.stack2:
return self.stack2.pop()
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self) -> int:
if not self.stack2:
return self.stack1[0]
else:
return self.stack2[-1]
def empty(self) -> bool:
if self.stack1 or self.stack2:
return False
return True
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
```
## Tree
### 144. Binary Tree Preorder Traversal
```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]:
res = []
def preorder(root):
if not root:
return
res.append(root.val)
preorder(root.left)
preorder(root.right)
preorder(root)
return res
```
### 94. Binary Tree Inorder Traversal
1. Recursion
```python
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def inorder(root):
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
inorder(root)
return res
```
2. Iterative
```python
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
res.append(curr.val)
curr = curr.right
return res
```
### 145. Binary Tree Postorder Traversal
```python
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def postorder(root):
if not root:
return
postorder(root.left)
postorder(root.right)
res.append(root.val)
postorder(root)
return res
```
### 102. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
```
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
```
```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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
q = deque()
curr = root
if not root:
return res
q.append(curr)
while q:
num = len(q)
level = []
for i in range(num):
curr = q.popleft()
level.append(curr.val)
if curr.left:
q.append(curr.left)
if curr.right:
q.append(curr.right)
res.append(level)
return res
```
### 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.
```
Input: root = [3,9,20,null,null,15,7]
Output: 3
```
```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:
if not root:
return 0
L_height = self.maxDepth(root.left)
R_height = self.maxDepth(root.right)
return max(L_height, R_height) + 1
```
### 101. Symmetric Tree
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
```
Input: root = [1,2,2,3,4,4,3]
Output: true
```
**Approach**
There are several situations
1. If the root is empty or the tree just has root node, then it is symmetric
2. Use two pointers to traverse both side, preoreder for left side and SRL for right side
3. If the node for both side is empty or have the same value, then is symmetric, otherwise is not
```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:
if ((not root) or (not root.left and not root.right)):
return True
def compare(lside, rside):
if (not lside and not rside):
return True
if (not lside or not rside):
return False
if lside.val != rside.val:
return False
return (compare(lside.left, rside.right) and compare(lside.right, rside.left))
return compare(root.left, root.right)
```
### 226. Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.
```
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
```
**Approach**
1. First invert the left subtree
2. Invert the right subtree
3. Invert the entire tree
```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]:
if not root:
return None
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
```
### 112. Path Sum
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
```
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
```
**Approach**
Use preorder traversal to scan the tree while compute the current sum
```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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, currSum):
if not node:
return False
currSum += node.val
if (not node.left and not node.right):
return currSum == targetSum
return (dfs(node.left, currSum) or dfs(node.right, currSum))
return dfs(root, 0)
```
### 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.
```
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
```
```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]:
curr = root
while curr:
if curr.val == val:
return curr
elif curr.val > val:
curr = curr.left
else:
curr = curr.right
return None
```
### 701. Insert into a Binary Search Tree
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.
Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.
```
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,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 insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
res = TreeNode()
res.val = val
if not root:
return res
curr, prev = root, None
while curr:
if curr.val > val:
prev = curr
curr = curr.left
else:
prev = curr
curr = curr.right
if prev.val > val:
prev.left = res
else:
prev.right = res
return root
```
### 98. Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left
subtree
of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
```
Input: root = [5,1,4,null,null,3,6]
Output: false
```
**Approach**
```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 isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(node, bottom, top):
if not node:
return True
if not (bottom < node.val and node.val < top):
return False
return (dfs(node.left, bottom, node.val) and dfs(node.right, node.val, top))
return dfs(root, -inf, inf)
```
### 653. Two Sum IV - Input is a BST
Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.
```
Input: root = [5,3,6,2,4,null,7], k = 9
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 findTarget(self, root: Optional[TreeNode], k: int) -> bool:
order = []
def inorder(node):
if not node:
return
inorder(node.left)
order.append(node.val)
inorder(node.right)
inorder(root)
need_val = {}
for i in range(len(order)):
if order[i] not in need_val:
need_val[k - order[i]] = i
else:
return True
return False
```
### 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).”
```
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.
```
```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':
curr = root
while curr:
if curr.val == p.val or curr.val == q.val:
return curr
elif curr.val > p.val and curr.val > q.val:
curr = curr.left
elif curr.val < p.val and curr.val < q.val:
curr = curr.right
else:
return curr
```
Sign in with Wallet
Connect another wallet