# Leetcode 101. Symmetric tree 對稱二叉樹

## 思路

1. 先確立邊界條件，因為這一題最小節點為 1 ，所以我們只要確認有沒有左右節點就可以了，分為兩種情況：
(1) 左右節點都不存在，代表只有根節點，所以樹是對稱的，回傳 True
(2) 如果只有一個節點不存在，代表樹不是對稱的，回傳 False
2. 使用中序遍歷遍歷左右子樹，而因為要驗證樹是否對稱的，所以要反轉左右其中一個子樹，這樣子在中序遍歷的時候，左右子樹的節點才會是一樣的。

**做這一題之前，可以先做：**
- leetcode 100 相同的樹
- leetcode 226 翻轉二叉樹

# 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: Optional[TreeNode]) -> bool:
        if not root.left and not root.right:
            return True
        if (not root.left and root.right) or (root.left and not root.right):
            return False
        
        stack = []
        cur_left = root.left
        cur_right = self.invertBinaryTree(root.right)

        while cur_left or cur_right or stack:
            if (not cur_left and cur_right) or (cur_left and not cur_right):
                return False 
            elif cur_left and cur_right:
                stack.append((cur_left, cur_right))
                cur_left = cur_left.left
                cur_right = cur_right.left
            elif not cur_left and not cur_right:
                node_left, node_right = stack.pop()
                if node_left.val != node_right.val:
                    return False
                cur_left = node_left.right
                cur_right = node_right.right
        return True
            
    def invertBinaryTree(self, root: TreeNode):
        if not root:
            return None
        
        root.left, root.right = root.right, root.left
        self.invertBinaryTree(root.left)
        self.invertBinaryTree(root.right)
        return root

2023.07.12 AC (DFS Recursion)

# 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: Optional[TreeNode]) -> bool:
        root.right = self.invertBinaryTree(root.right)
        return self.isSameTree(root.left,root.right)

    def isSameTree(self,p: TreeNode, q: TreeNode):
        if not p and not q:
            return True
        if (not p and q) or (not q and p) or p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        
    def invertBinaryTree(self,root: TreeNode):
        if not root:
            return None
        self.invertBinaryTree(root.left)
        self.invertBinaryTree(root.right)
        root.left,root.right = root.right, root.left
        return root