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

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 Falseresult = []stack = []cur = rootwhile cur or stack:if cur:stack.append(cur)cur = cur.leftelse:cur = stack.pop()result.append(cur.val)cur = cur.rightindex = int(len(result)//2)return result[:index] == result[index+1:][::-1]

特殊情况下不能通过：

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

正确思路

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

递归法

递归三部曲

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

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

2. 确定终止条件

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

3. 确定单层递归的逻辑

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

# 递归法
class Solution(object):def isSymmetric(self, root):if not root:return True # 树为空也是返回Truereturn self.compare(root.left, root.right)def compare(self, left, right): # 递归第一点: 参数应该传入什么 返回类型为布尔# 递归第二点: 什么时候终止 一个有空 / 值不同# 排除节点为空的情况if left and not right: # 1. 有空情况：左不为空 右为空return Falseelif not left and right: # 2. 有空情况：左为空 右不为空return Falseelif not left and not right: # 3. 有空情况：都为空 Truereturn Trueelif 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 Truequeue = 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 Falsequeue.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 Falsestack.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 = valself.left = leftself.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 Falseelif left and not right:return Falseelif not left and not right:return Trueelif left.val != right.val:return Falseoutside = 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 = valself.left = leftself.right = rightclass Solution(object):def isSubtree(self, root, subRoot):""":type root: TreeNode:type subRoot: TreeNode:rtype: bool"""if not root and not subRoot:return Trueif not root or not subRoot:return Falseif root.val == subRoot.val:if self.compare(root, subRoot):return Truereturn self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)  # 看root树的左右子树是否有subRootdef compare(self, p , q): # p q 代表两棵树 参数# 终止条件if not p and not q:return Trueif not p or not q:return Falseif p.val != q.val:return Falsereturn self.compare(p.left, q.left) and self.compare(p.right, q.right)