1. Immutable Types
https://neetcode.io/problems/kth-smallest-integer-in-bst
여기서 배열은 nested 되어있는 inorder 밖에서 선언되었음에도 함수 내에서 append가 가능하다.
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
ans = []
def inorder(root) :
if root :
inorder(root.left)
ans.append(root.val)
inorder(root.right)
inorder(root)
return ans[k-1]
하지만 밑의 함수에서는 def inorder 안에 nonlocal curr와 ans를 선언해주지 않으면 UnboundLocalError: cannot access local variable 'curr' where it is not associated with a value
에러가 뜬다.
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
curr= 0
ans = 0
def inorder(root) :
nonlocal curr, ans
if root :
inorder(root.left)
curr = curr + 1
if curr == k :
ans = root.val
inorder(root.right)
inorder(root)
return ans
ans 같은 리스트는 가능한데 curr나 ans같은 int type은 왜 def inorder 함수 안에서 수정이 불가능한 것일까?
그것은 int가 파이썬의 immutable data type 중 하나이기 때문이다.
immutable data type은 값을 변경을 못하고 새로운 객체를 생성한다. 따라서, 함수 밖의 curr와 ans를 참조하지 못하고 inorder 함수 내에서 새로운 local 변수라 가정하고 새로운 객체를 생성하는 것이다. 따라서 nonlocal curr, ans를 선언해줌으로써 local이 아닌 밖에서 선언된 curr와 ans를 참조할수 있는 것이다.
밑의 설명을 읽어봐라.
Python Immutable Data types 관련 설명 블로그 글 : https://velog.io/@chobe1/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B8%B0%EC%B4%88-Mutable-vs-Immutable-Objects
참고로 nested 함수를 하지 않고 푸는 방식도 있었다.
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
curr = root
stack = []
curr_k= 0
while (curr or stack) :
while curr :
stack.append(curr)
curr= curr.left
curr = stack.pop()
curr_k += 1
if curr_k == k :
return curr.val
curr= curr.right
return ans[k-1]
2. Inorder Traversal의 두 가지 방식 (Iterative, Recursive)
https://neetcode.io/courses/dsa-for-beginners/19
Recursive
def inorderTraversal(self, root):
array = []
def inorder(root):
if root:
inorder(root.left)
array.append(root.val)
inorder(root.right)
inorder(root)
return array
Iterative
def inorderTraversal(self, root):
curr = root
stack = []
ans = []
while (curr or stack) :
while curr :
stack.append(curr)
curr= curr.left
curr = stack.pop()
ans.append(curr.val)
curr= curr.right
return ans
3. preorder와 inorder로 tree build하기
어떠한 tree의 preorder와 inorder sequence를 알면 tree를 100% 복원 가능하다.
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder :
return None
mid = inorder.index(preorder[0])
root = TreeNode(preorder[0])
root.left=self.buildTree(preorder[1:mid+1], inorder[:mid])
root.right=self.buildTree(preorder[mid+1:],inorder[mid+1:])
return root