[Leetcode] 101. Symmetric Tree

7430 ワード
easy leetcode tree コーディングテスト テキストリンク
問題のショートカット
基本的な解法は同じであるが,再帰はサイクルよりほぼ2倍速い.これはlistの頻繁な追加と削除による違いです.

Loop


Time Complexity: O(n)O(n)O(n)
Space Complexity: O(log⁡n)O(\log n)O(logn)
# 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 isSymmetric(self, root: TreeNode) -> bool:
        stack = [(root.left, root.right)]
        
        while stack:
            leftTop, rightTop = stack.pop()
            if leftTop is None and rightTop is None:
                continue
            if leftTop is None or rightTop is None:
                return False
            if leftTop.val != rightTop.val:
                return False    
            stack.append((leftTop.left, rightTop.right))
            stack.append((leftTop.right, rightTop.left))
        return True

Recursion


Time Complexity: O(n)O(n)O(n)
Space Complexity: O(log⁡n)O(\log n)O(logn)
# 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 isSymmetric(self, root: TreeNode) -> bool:
        def symmetric_helper(root1, root2):
            if root1 is None and root2 is None:
                return True
            if root1 is None or root2 is None:
                return False
            if (root1.val == root2.val and 
                symmetric_helper(root1.right, root2.left) and 
                symmetric_helper(root1.left, root2.right)):
                return True
            return False
        
        return symmetric_helper(root.left, root.right)
JS非同期関数、promise
posts/show.html.erb