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

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

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

[LeetCode][Easy] 145. Binary Tree Postorder Traversal


https://leetcode.com/problems/binary-tree-postorder-traversal/

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        self.dfs(root, ans)
        return ans
        
    def dfs(self, node, ans):
        if not node:
            return node
        
        self.dfs(node.left, ans)
        self.dfs(node.right, ans)
        ans.append(node.val)

[LeetCode][Medium] 102. Binary Tree Level Order Traversal


https://leetcode.com/problems/binary-tree-level-order-traversal/

BFS で解こうとしたけど、Python でキューをどうすればいいのか知らなかったので、DFS で解いた。キューの使い方勉強しないとなぁ。。

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        
        def dfs(node, level, ans):
            if not node:
                return
            
            if len(ans) == level:
                ans.append([])

            ans[level].append(node.val)
            dfs(node.left, level + 1, ans)
            dfs(node.right, level + 1, ans)
            
        dfs(root, 0, ans)
        return ans

[LeetCode][Easy] 104. Maximum Depth of Binary Tree


https://leetcode.com/problems/maximum-depth-of-binary-tree/

DFS の再帰コールで解く。

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

スタックを使ってみる

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        ans = 0
        stack = [(1, root)]
        while stack:
            depth, node = stack.pop()
            ans = max(ans, depth)
            
            if node.left is not None:
                stack.append((depth + 1, node.left))
            if node.right is not None:
                stack.append((depth + 1, node.right))
            
        return ans

[LeetCode][Easy] 101. Symmetric Tree


https://leetcode.com/problems/symmetric-tree/

これ、思い付けば簡単だけど、Easyレベルなのか?

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def helper(node1, node2) -> bool:
            if node1 is None and node2 is None:
                return True
            
            if node1 is None or node2 is None:
                return False
            
            return node1.val == node2.val and helper(node1.left, node2.right) and helper(node1.right, node2.left)
            
        return helper(root, root)

[LeetCode][Easy] 112. Path Sum


https://leetcode.com/problems/path-sum/

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False

        targetSum -= root.val
        if not root.left and not root.right:
            return targetSum == 0
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)


See also