본문 바로가기

Recursion10

[자료구조] 이진탐색 (Binary Search) 파이썬 (bisect, recursion, iteration) 일반적인 풀이방법 def solution(L, x): start, end = 0, len(L)-1 while start = low: mid = (high + low) // 2 # If element is present at the middle itself if arr[mid] == x: return mid # If element is smaller than mid, then it can only # be present in left subarray elif arr[mid] > x: return binary_search(arr, low, mid - 1, x) # Else the element can only be present in right subarray else: return binary_search.. 2021. 4. 20.
[LeetCode] Binary Tree Paths 파이썬 (Binary Tree, LCA, DFS) class Solution(object): # @param {TreeNode} root # @return {string[]} def binaryTreePaths(self, root): result, path = [], [] self.binaryTreePathsRecu(root, path, result) return result def binaryTreePathsRecu(self, node, path, result): if node is None: return if node.left is node.right is None: ans = "" for n in path: ans += str(n.val) + "->" result.append(ans + str(node.val)) if node.left: path... 2021. 4. 7.
[LeetCode] Path Sum 파이썬 class Solution: # @param root, a tree node # @param sum, an integer # @return a boolean def hasPathSum(self, root, sum): if root is None: return False if root.left is None and root.right is None and root.val == sum: return True return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val) sum - curr_value 하면서 left, right node를 계속 탐색하다가 leaf 에 도착했을때 curr_value =.. 2021. 4. 1.
[LeetCode] Minimum Depth of Binary Tree 파이썬 (recursion) class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # @param root, a tree node # @return an integer def minDepth(self, root): if root is None: return 0 if root.left and root.right: return min(self.minDepth(root.left), self.minDepth(root.right)) + 1 else: return max(self.minDepth(root.left), self.minDepth(root.right)) + 1 max와 다른 점은 leaf node 까지의.. 2021. 4. 1.
[LeetCode] Balance Binary Tree python 파이썬 (recursion) # 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(object): def maxDepth(self, root): if root == None: return 0 else: return max( self.maxDepth(root.left), self.maxDepth(root.right)) + 1 def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ if root == No.. 2021. 4. 1.
[LeetCode] Convert Sorted Array to Binary Tree python 파이썬 (recursion, median) 솔루션을 보기 전에는 어떤식으로 풀어야 하는지 감이 안왔다. 솔루션을 보고 나니 Binary Search 개념을 사용해서 mid 지점만 root 가 되도록 하면 되는 것이다. class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def sortToBST(nums): if len(nums) == 0: return None mid = nums[len(nums) // 2] root = TreeNode(mid) root.left = sortToBST(nums[:len(nums) // 2]) root.right = sortToBST(nums[len(nums) // 2 + 1:]) return root return sortToBST(num.. 2021. 4. 1.
[LeetCode] Maximum Depth of Binary Tree 파이썬 (recursion) 40ms class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # @param root, a tree node # @return an integer def maxDepth(self, root): if root is None: return 0 else: return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 출처:github.com/jiapengwen/LeetCode/blob/master/Python/maximum-depth-of-binary-tree.py class Solution: def maxDepth(se.. 2021. 3. 31.
[LeetCode] Symmetric Tree 파이썬 (iterative, recursion) iterative solution (32ms) class Solution: # @param root, a tree node # @return a boolean def isSymmetric(self, root): if root is None: return True stack = [] stack.append(root.left) stack.append(root.right) while stack: p, q = stack.pop(), stack.pop() if p is None and q is None: continue if p is None or q is None or p.val != q.val: return False stack.append(p.left) stack.append(q.right) stack.ap.. 2021. 3. 31.
[LeetCode] Same Tree 파이썬 (TreeNode, recursion) class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # @param p, a tree node # @param q, a tree node # @return a boolean def isSameTree(self, p, q): if p is None and q is None: return True if p is not None and q is not None: return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) return False 출처: github.com.. 2021. 3. 31.

티스토리툴바