[leetcode] 3-2회차

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/?envType=study-plan-v2&envId=top-interview-150

 

저번과 마찬가지로 접근하면 될 것 같다. 그런데 약간 로직은 변경하긴 해야겠다..

접근 법 : postorder 의 맨 마지막은 루트인 편이다. 그러므로 오른쪽으로 가면서 하면 저번에 푼 preorder 과 마찬가지로 풀릴 수 있다.

# 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 buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: Optional[TreeNode]
        """
        if not inorder:
            return None
        
        left = []
        right = []
        parentVal = postorder.pop()
        
        for i in range(len(inorder)):
            if inorder[i] == parentVal:
                left = inorder[:i]
                right = inorder[i+1:]
                break
        parent = TreeNode(parentVal)
        parent.right = self.buildTree(right, postorder)
        parent.left = self.buildTree(left, postorder)

        return parent
        

        # inorder : 왼 -> 루트 -> 오
        # postorder : 왼 -> 오 -> 루트

 

간단하게 해결되었다!

 

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

class Solution:
    def connect(self, root):
        if not root:
            return None

        q = deque()
        q.append(root)
        dummy = Node(-999)

        while q:
            length = len(q)

            prev = dummy
            for _ in range(length):
                popped=q.popleft()
                if popped.left:
                    q.append(popped.left)
                    prev.next = popped.left
                    prev=prev.next
                if popped.right:
                    q.append(popped.right)
                    prev.next = popped.right
                    prev = prev.next
                
        return root

 

 

오늘 신기한 경험을 해서 조금이나마 적어본다..

오늘 카페에서 공부를 하고 있었는데, 사람들이 친절하게 대해주셨다. 무려 3분이나...

 

서울 상경해서 이런 경험을 한게 신기하기도 했고, 사람들이 친절하다고 생각했다.

조금 답답한 생활이라고 생각했는데, 정도 느껴지고 좋은 하루인 것 같다.