tree 문제 2개 [leetcode]

첫번째 문제

Increasing Order Search Tree

이진 트리를 가장 작은 수부터 차례대로 오른쪽 자식 노드로 이어 붙이는 문제였다.

이진 트리의 경우, 숫자 크기에 따라 현재 노드보다 작으면 left, 크면 right 로 붙어있다.

그렇기 때문에 아래 규칙으로 재귀를 만들면 된다.

1. left 노드의 가장 오른쪽 (right leaf) 의 오른쪽 가지에 node를 이어 붙인다.
   1. left 가 존재하지 않으면 해당 순서를 무시
2. node의 오른쪽 가지에 right 노드를 이어 붙인다.
   1. right 가 존재하지 않으면 해당 순서를 무시
3. left를 반환한다. (새로운 root가 된다.)
   1. left가 없었다면 node 를 반환

def reConnect(self, node):
    if node == None:
        return None
    else:
        left = None
        if node.left != None:
            left = self.reConnect(node.left)
		# 해당 재귀를 통해 left쪽 가지가 right하게 정렬되서 반환
                
        right = None
        if node.right != None:
            right = self.reConnect(node.right)
		# 해당 재귀를 통해 right 쪽 가지가 right하게 정렬되서 반환
            
        if left != None: #left가 존재한다면 node를 left의 최우측에 붙여야함
            # left node last connect
            curr = left
            while curr.right != None:
                curr = curr.right
            curr.right = node
            
            if right != None:
                node.right = right
            node.left = None
            return left
        elif left == None and right != None: # right만 존재한다면 node의 right를 이어 붙힘
            node.right = right
            node.left = None
            return node
        else: # 아니라면 node만 반환
            return node

 

두번째 문제

Trim a Binary Search Tree

위 문제와는 다르게 low와 high를 통해 해당 범위 내 숫자들만 반환한다.

(대신 정렬은 수행하지 않는다.)

위 그림과 같이 해당 범위내 숫자를 가진 가지들만 위치를 유지한 채

(left 가지였으면 left 측, right 가지 였으면 right측 ⇒ 이진트리를 유지)

반환해야 한다.

 

위 문제의 까다로운 점은 노드 숫자가 범위내 숫자가 아닐지라도 해당 노드의 자식노드들 중에 범위내 숫자가 존재 할 수 있으므로 전부 확인해야 하는 단점이 있다.

 

규칙을 서술하자면,

1. node의 숫자를 확인한다.
2. node의 숫자가 low 보다 작다면 right 노드를 확인한다. (이진 트리임으로 left는 자동으로 범위 이탈)
   • right 노드의 숫자가 범위내라면 right 노드 return (재귀함수를 통해 right 노드는 범위 내 숫자만 들어있음)
3. node의 숫자가 high 보다 크다면 left 노드를 확인한다. (이진 트리임으로 right는 자동으로 범위 이탈)
   • left 노드의 숫자가 범위 내 라면 left 노드 return (재귀함수를 통해 left 노드는 범위 내 숫자만 들어있음)

def reconnect(self, node, low, high):
  if node == None:
      return None
  else:
      left = None
      if node.left != None:
          left = self.reconnect(node.left, low, high)
          # 해당 재귀를 통해 left 가지는 범위내 숫자들 만 존재                 
      right = None
      if node.right != None:
          right = self.reconnect(node.right, low, high)
              # 해당 재귀를 통해 right 가지는 범위내 숫자들 만 존재
      if node.val > high: # node 숫자가 high 보다 크다면 right는 볼필요 x
          if left != None and low <= left.val and left.val <= high:
              return left
          else:
              return None
      elif node.val < low: # node 숫자가 left 보다 크다면 left는 볼필요 x
          if right != None and low <= right.val and right.val <= high:
              return right
          else:
              return None
      else: # node가 범위 내 라면
          if left == None:
              node.left = None
          else:
              node.left = left #node 의 왼쪽을 연결

          if right == None:
              node.right = None
          else:
              node.right = right #node의 오른쪽을 연결

          return node

두번째 문제는 풀이를 적다보니 알게된게

node 의 숫자가 범위보다 작으면 left 가지를 재귀 함수로 돌릴 필요가 없고,

node 의 숫자가 범위보다 크다면 right 가지를 재귀 함수로 돌릴 필요가 없다.

(그럼 시간을 좀 더 단축할 수 있을 것이다.)