力扣刷题-二叉树-对称二叉树

101 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。
示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

思路

我的思路-中序遍历

利用中序遍历（左中右），遍历树，然后根据遍历结果根节点两边左右是否是相反的，如果是那么就是对称的。

比如这个，遍历结果为 3 2 4 1 4 2 3 ，在根节点两边，324和423是相反的，说明是对称的**——>错误！！！**

# 可以用中序遍历
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return False
        result = []
        stack = []
        cur = root
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right
        index = int(len(result)//2)
        return result[:index] == result[index+1:][::-1]

特殊情况下不能通过：

在这个例子下不能通过。
就是根节点左右两边一模一样，但是却有可能不是对称二叉树。

正确思路

首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
那么如何比较呢？
比较的是两个子树的里侧和外侧的元素是否相等。如图所示：

递归法

递归三部曲

确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。

确定终止条件

要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true
此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
左右都不为空，比较节点数值，不相同就return false
此时左右节点不为空，且数值也不相同的情况我们也处理了。

确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。
比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false 。

# 递归法
class Solution(object):
    def isSymmetric(self, root):
        if not root:
            return True # 树为空也是返回True
        return self.compare(root.left, root.right)
    
    def compare(self, left, right): # 递归第一点: 参数应该传入什么 返回类型为布尔
        # 递归第二点: 什么时候终止 一个有空 / 值不同
        # 排除节点为空的情况
        if left and not right: # 1. 有空情况：左不为空 右为空
            return False
        elif not left and right: # 2. 有空情况：左为空 右不为空
            return False
        elif not left and not right: # 3. 有空情况：都为空 True
            return True
        elif left.val != right.val: # 3. 无空情况：值不相同
            return False
        # 递归第三点：单层逻辑
        # 此时就是：左右节点都不为空，且数值相同的情况
        # 此时才做递归，做下一层的判断
        outside = self.compare(left.left, right.right) # 外侧
        inside = self.compare(left.right, right.left) # 内侧
        return outside and inside # 比较内外侧是否相同

迭代法-使用队列

队列，需要注意的是这不是层序遍历，而且仅仅通过一个容器来成对的存放我们要比较的元素。
核心思想就是：比较左右子树里侧和外侧是否相等

# 迭代法
from collections import deque
class Solution(object):
    def isSymmetric(self, root):
        if not root:
            return True
        queue = deque([root.left, root.right])
        while queue:
            left = queue.popleft()
            right = queue.popleft()
            # if (not left and right) or (left and not right) or (left.val != right.val):
            #     return False 错误写法
            if not left and not right:
                continue # 左右都为空 继续
            if not left or not right or left.val != right.val: # 返回False的情况
                return False
            queue.append(left.left) # 左节点左孩子
            queue.append(right.right) # 右节点右孩子
            queue.append(left.right) # 左节点右孩子
            queue.append(right.left) # 右节点左孩子
        return True

迭代法-使用栈

# 迭代法
class Solution(object):
    def isSymmetric(self, root):
        if not root:
            return True
        # queue = deque([root.left, root.right])
        stack = []
        stack.append(root.left)
        stack.append(root.right)
        while stack:
            left = stack.pop()
            right = stack.pop()
            # if (not left and right) or (left and not right) or (left.val != right.val):
            #     return False 错误写法
            if not left and not right:
                continue # 左右都为空 继续
            if not left or not right or left.val != right.val: # 返回False的情况
                return False
            stack.append(left.left) # 左节点左孩子
            stack.append(right.right) # 右节点右孩子
            stack.append(left.right) # 左节点右孩子
            stack.append(right.left) # 右节点左孩子
        return True

100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：

输入：p = [1,2,3], q = [1,2,3] 输出：true
直接使用递归主函数传入的不一样罢了上一题是根节点左右节点这一题是两棵树（用根节点表示）

递归

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 isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        return self.compare(p, q) # 直接调用即可 compare 包含了其中逻辑
    
    def compare(self, left, right): # 也是比较左右子树是否相同 同样从里侧和外侧 考虑
        if not left and right:
            return False
        elif left and not right:
            return False
        elif not left and not right:
            return True
        elif left.val != right.val:
            return False
        outside = self.compare(left.left, right.left)
        inside = self.compare(left.right, right.right)
        return outside and inside

572. 另一棵树的子树

双递归有难度

核心找到一个节点相同了把这个视为root再一次的根节点从这个开始找调用 compare

compare目的就是找到root起始节点与subRoot一致的时候开始比较两棵树
而主函数是为了找到这样的一个root起始节点

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 isSubtree(self, root, subRoot):
        """
        :type root: TreeNode
        :type subRoot: TreeNode
        :rtype: bool
        """
        if not root and not subRoot:
            return True
        if not root or not subRoot:
            return False
        if root.val == subRoot.val:
            if self.compare(root, subRoot):
                return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)  # 看root树的左右子树是否有subRoot
    
    def compare(self, p , q): # p q 代表两棵树 参数
        # 终止条件
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        
        return self.compare(p.left, q.left) and self.compare(p.right, q.right)