101. 对称二叉树

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

进阶:

  • 你可以运用递归和迭代两种方法解决这个问题吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一解

使用递归,双指针 p,q 指向树的左右节点:

    1
   / \
  2 p 2 q
 / \ / \
3  4 4  3

利用 p 和 q 进行递归判断:

  • 终止条件:
    • 越过叶节点,返回 true
    • p,q 只有一个为空,返回 false
  • 递推工作:
    • 同时递归 p 左子树和 q 的右子树,返回值为 r1
    • 同时递归 q 左子树和 p 的右子树,返回值为 r2
  • 返回值:
    • r1,r2 全部为 true 并且 p.val == q.val :此时 p 和 q 是镜像对称,返回 true
    • 否则:不对称,返回 false
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def check(p, q):
            if not p and not q: return True
            if not p or not q: return False
            return p.val == q.val and check(p.left, q.right) and check(p.right, q.left)

        return check(root, root)
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

二解

利用迭代法,使用栈模拟递归调用:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        stack = [root, root]
        while stack:
            u, v = stack.pop(), stack.pop()
            if not u and not v: continue
            if not u or not v or u.val != v.val: return False
            stack.append(u.left)
            stack.append(v.right)
            stack.append(u.right)
            stack.append(v.left)
        return True
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
关闭