[leetcode]100, 101same tree/Symm

题目

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 :方法类似上面，调整入栈顺序即可