题目
100 same tree
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
101 symetic tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
分析
判断一棵二叉树本身是否是镜像对称 / 相等的，可以转化为：二叉树的左子树与右子树是否是镜像对称 / 相等的。
使用递归法
same tree:判断 l 和 r 值相等， 并且，l 的左子树与r 的左子树相等，l 的右子树与r 的右子树相等
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if not p and not q:
return True
if not p or not q:
return False
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
symmetric tree: 判断 l 和 r 值相等， 并且，l 的左子树与r 的右子树相等，l 的右子树与r 的左子树相等
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# run by Python3
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True #当树为空时，为对称树
return self.symmetric(root.left, root.right)
def symmetric(self, l: TreeNode, r:TreeNode):
if not l and not r:
return True # 左子树与右子树都为空，对称
if not l or not r:
return False # 左子树与右子树其一为空，不对称
return l.val == r.val and self.symmetric(l.left, r.right) and self.symmetric(l.right, r.left)
使用递归法
symmetric tree: 设置一个栈， 依次吧 l 的左子树、r 的右子树，l 的右子树， r的左子树压入栈中， 每次判断栈顶的两个元素是否相。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
stack = []
stack.append(root.left)
stack.append(root.right)
while stack:
l = stack.pop()
r = stack.pop()
if not l and not r:
continue
if not l or not r or l.val != r.val:
return False
stack.append(l.left)
stack.append(r.right)
stack.append(l.right)
stack.append(r.left)
return True
same tree :方法类似上面，调整入栈顺序即可
