Leetcode 101. 对称二叉树

心路历程：

这道题没有想象中那么简单。其最难的地方就在于如何判断两个子树相等这件事上，无法直接left == right，因为毕竟只是指针。
本道题思考了三种解法，其中一种很可惜没有完全AC。

注意的点：

1、root.left == root.right 这样判断两个子树是不是相等是没有意义的。
2、一个递归函数是可以同时遍历两个树的，同时遍历还是很有意思，之前没有遇到过。
3、中序遍历虽然可以按照搜索树顺序获得值，但是当值相等时容易误判。

解法一：直接双node递归判断

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # 思路三：直接判断左右子树是否镜像对称即可
        if not root.left: return root.right is None
        def dfs(node1, node2):  # 同时遍历两个结点并比较
            if not node1: return node2 is None
            if not node2: return node1 is None
            current_level = node1.val == node2.val
            child1_level = dfs(node1.left, node2.right)
            child2_level = dfs(node1.right, node2.left)
            return current_level and child1_level and child2_level
        return dfs(root.left, root.right)

解法二：先翻转左子树，再判断左右子树是否相等（相比于解法一有点多此一举）

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # 思路二：直接翻转其左子树，判断左子树全部反转后是否与右子树相同
        def fanzhuan(node):
            if not node: return
            node.left, node.right = node.right, node.left  # 这样操作是没问题的
            fanzhuan(node.left)
            fanzhuan(node.right)

        if not root.left:
            return root.right is None
        fanzhuan(root.left)

        # return root.left == root.right  # 这样判断能行吗？ -> 不行
        def dfs(node1, node2):  # 同时遍历两个结点并比较
            if not node1: return node2 is None
            if not node2: return node1 is None
            
            current_level = node1.val == node2.val
            left_level = dfs(node1.left, node2.left)
            right_level = dfs(node1.right, node2.right)
            return current_level and left_level and right_level
        return dfs(root.left, root.right)

AC 97%的做法三：利用中序的性质+双指针判断是否回文

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # 思路一：利用中序遍历的有序性 -> 不行，因为可能值会重复 root = [1,2,2,2,null,2]时; 97% AC
        def dfs(node):
            if not node: return []
            return dfs(node.left) + [node.val] + dfs(node.right)
        res = dfs(root)
        n = len(res)
        print(res)
        if n % 2 == 0: return False
        left, right = 0, n-1
        while left < right:
            if res[left] == res[right]:
                left += 1
                right -= 1
            else:
                return False
        return True