プログラミングトレーニング(06/17/2021)

プログラミングトレーニング(06/17/2021)

競技プログラミングの練習メモです。

[LeetCode][Medium] 106. Construct Binary Tree from Inorder and Postorder Traversal


https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

解けなかった…。要復習

    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None
            
            val = postorder.pop()
            root = TreeNode(val)

            root.right = helper(hash_inorder[val] + 1, right)
            root.left = helper(left, hash_inorder[val] - 1)

            return root

        hash_inorder = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(postorder) - 1)

[LeetCode][Medium] 105. Construct Binary Tree from Preorder and Inorder Traversal


https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

pop(0) を使っているのが微妙で index を進めていく方が良いとは思うけど、いずれにせよ上記の問題と同じなので解けた。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None
            
            val = preorder.pop(0)
            root = TreeNode(val)
            root.left = helper(left, inorder_hash[val] - 1)
            root.right = helper(inorder_hash[val] + 1, right)
            return root
            
        inorder_hash = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(preorder) - 1)

[LeetCode][Medium] 116. Populating Next Right Pointers in Each Node


https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

キューを使う方法なら簡単だけど、Space O(1) の方法は思い付かなかった。

import collections

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return root

        q = collections.deque([root])

        while q:
            size = len(q)
            for i in range(size):
                node = q.popleft()
                if i != size - 1:
                    node.next = q[0]
                
                if node.left is not None or node.right is not None:
                    q.append(node.left)
                    q.append(node.right)
            
        return root

[LeetCode][Medium] 117. Populating Next Right Pointers in Each Node II


https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

上記の問題と同じ。

import collections

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        
        q = collections.deque()
        q.append(root)
        while q:
            size = len(q)
            for i in range(size):
                node = q.popleft()
                if i != size - 1:
                    node.next = q[0]

                if node.left is not None:
                    q.append(node.left)
                    
                if node.right is not None:
                    q.append(node.right)
        
        return root

[LeetCode][]





See also