問題
原文
Given the
rootof a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
Constraints:
- The number of nodes in the tree is in the range
[1, 1000].-100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
内容
二分木であるrootが与えられます。左右対称(根ノードを中心に対称であるか)になっているかを確認してください。
制約
・ノードの数は1~1000
・各ノードの値は-100~100
再帰と反復のそれぞれで解いてみてください。
※正しくない可能性があります。
方針
反復で解答する際はキューを用いています。
解答
解答1 反復➀
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
from collections import deque class Solution(object): def isSymmetric(self, root): #親ノードがない場合 if root is None: #Trueを返す return True #qにdequeで親ノードを入れる q = deque([root]) print("q:",q) #qに要素がある限り続ける while q: #qの要素数を取得 size = len(q) #numsを初期化 nums = [] #qの要素数だけ繰り返す for i in range(size): #nodeにqの左端の要素(親ノード)を入れる node = q.popleft() #nodeの左側の子ノードがある場合 if node.left != None: #qにnodeの左側の子ノードの子ノードを入れる q.append(node.left) #numsにnodeの左側の子ノードの値を入れる nums.append(node.left.val) #nodeの左側の子ノードがない場合 else: #numsにNondeを入れる nums.append(None) #nodeの右側の子ノードがある場合 if node.right != None: #qにnodeの右側の子ノードを入れる q.append(node.right) #numsにnodeの右側の子ノードの値を入れる nums.append(node.right.val) #nodeの右側の子ノードがない場合 else: #numsにNoneを入れる nums.append(None) print(nums) #numsと逆順のnumsが不一致なら if nums != list(reversed(nums)): #Falseを返す return False #qから要素がなくなればTrueを返す return True |
解答2 反復②
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: #親ノードがない場合 if not root: #Trueを返す return True #qにdequeで左右の子ノードを入れる q = collections.deque([(root.left, root.right)]) #qにノードがある限り繰り返す while q: #node1,node2にqの左端の要素を入れる node1,node2 = q.popleft() #node1,node2の両方に要素がない場合 if not node1 and not node2: #無視 continue #node1かnode2のいずれかの要素がない場合 if not node1 or not node2: #Falseを返す return False #node1とnode2の親ノードの値が不一致の場合 if node1.val != node2.val: #Falseを返す return False #qにnode1の左側の子ノード・node2の右側の子ノードを入れる q.append((node1.left, node2.right)) #qにnode1の右側の子ノード・node2の左側の子ノードを入れる q.append((node1.right, node2.left)) #qから要素が全てなくなったらTrueを返す return True |
解答3 再帰
これは頑張って後日解答したいと思います。
補足・参考・感想
前回の問題と似ていますね。まだ一回目なのでまずは中身を理解することに重点を置いています。
今後、繰り返し解いていく中でまずはミスなくコーディングできること。面接を意識していくつかの解法とその比較を日本語で説明できること。最後に英語でそれらをホワイトボードに書きながら実行すること。と言った具体に少しずつステップアップしていきたいと思いました。
コメント