Symmetric Tree in python
2039 ワード
質問リンク
https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/627/
問題を解く構想.
方法1
遍歴whileサイクルエラーポイント:whileサイクル内でqrをqlと書き、キューが空になる改善点:Queueメソッドを使用し、効率が遅い
方法2
再帰法は反復法と類似しており,左右の順序に注意する.
https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/627/
問題を解く構想.
方法1
遍歴whileサイクルエラーポイント:whileサイクル内でqrをqlと書き、キューが空になる改善点:Queueメソッドを使用し、効率が遅い
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import Queue
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
ql = Queue.Queue()
qr = Queue.Queue()
ql.put(root.left, False)
qr.put(root.right, False)
while not ql.empty() and not qr.empty():
nl = ql.get(False)
nr = qr.get(False)
if (nl and not nr) or (not nl and nr):
return False
if nl:
if nl.val != nr.val:
return False
ql.put(nl.left, False)
ql.put(nl.right, False)
qr.put(nr.right, False)
qr.put(nr.left, False)
return True
方法2
再帰法は反復法と類似しており,左右の順序に注意する.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.sym(root.left, root.right) if root else True
def sym(self, left, right):
if not left and not right:
return True
if not left:
return False
if not right:
return False
if left.val != right.val:
return False
return self.sym(left.left, right.right) and self.sym(left.right, right.left)