문제: Search in a Binary Search Tree
등급: Easy
내용: 이진 트리와 val가 주어지는데, 이진트리에서 val를 찾아야함.
<코드>
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def searchBST(self, root, val):
if not root:
return None
if root.val == val:
return root
return self.searchBST(root.left, val) or self.searchBST(root.right,val)
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
오, 이게 되네...
<논리>
굉장히 간단한 코드이다. root가 없으면, None을 반환하고, root.val ==val일 경우, root을 반환한다.
그리고, 계속 재귀 호출을 통해 breadth-first-search, 너비 우선 탐색을 통해 찾아준다. 계속 root가 node도 아니고, ==val도 아니라면 root.left와 root.right로 계속 호출해줘서 찾는 것이다.
만약에, root.val==val 한 번이라도 된다면, self.searchBST(root, val)는 True가 되기 때문에 그 treenode가 반복되는 호출 속에서 나오게 된다.
<총평>
오 내가 하나 풀다니
Happy coding!
'코딩 공부' 카테고리의 다른 글
Leetcode Fibonacci Number 파이썬 풀이 (0) | 2022.02.02 |
---|---|
Leetcode Pascal's Triangle II 파이썬 풀이 (0) | 2022.02.01 |
Leetcode: Reverse Linked List python 풀이 (0) | 2022.01.28 |
Leetcode recursion (재귀): Swap Nodes in Pair 파이썬 풀이 (0) | 2022.01.26 |
댓글