# Symmetric Tree
###### tags: `Easy`、`Tree`

## 非遞迴解
- 想法:將每層的節點存到q這個雙向儲列中，每層數值存到level中，再檢查儲列反轉前後是否相同，就這樣逐層檢查

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # iterative solution
        q = deque()
        q.append(root)
        while len(q):  #該層有節點(值)就會執行
            level = []
            length = len(q)
            for _ in range(length): #執行節點個數次
                current = q.popleft()  #每次向右移一個節點
                if current.val == float("inf"):
                    level.append(current.val) 
                    continue
                else:
                    level.append(current.val) 
                    if current.left:     #確認節點的右子節點有沒有值
                        q.append(current.left)
                    else:
                        temp = TreeNode(val=float("inf"))
                        q.append(temp)

                    if current.right:    #確認節點的左子節點有沒有值
                        q.append(current.right)
                    else:
                        temp = TreeNode(val=float("inf"))
                        q.append(temp)    
            # 到這邊就決定好下一層有幾個節點了
            print("-------")
            print(q)
            print(level)
            if level == level[::-1]:  #反轉後相比
                continue
            else: 
                return False    
        return True  

## 遞迴解
- 想法:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def check_symmetry(left_node, right_node):
            if left_node and right_node:
                return (left_node.val == right_node.val and 
                check_symmetry(left_node.left, right_node.right) and check_symmetry(left_node.right, right_node.left))
            return left_node is right_node

        return check_symmetry(root.left, root.right)