288443db60094f215dc841cc41a50b97
(难度Easy) Problem 101. Symmetric Tree(对称二叉树)

Symmetric Tree

Difficulty

Easy

Description

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

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

題解

这道题虽然标着Easy,但是想要一下子想到解法还是不太容易,不过好在题目当中给了我们提示:最好是使用递归或者迭代的方式来解决。

我们都知道递归是把一个大问题转化成子问题来解决,那么对于当下这个问题而言,我们应该怎么使用递归呢?

我们可以先来分析一下二叉树的性质,对于一棵二叉树而言,它自身是对称的,意味着它的左右子树互相对称。对于它的左右子树而言,这一点同样成立。

假设当前节点为rt,它的左节点是l,右节点是r,那么显然l==r。如果l的左节点是ll,右节点是lr,r的左节点是rl,右节点是rr。那么显然ll==rr,lr=rl。那么我们写成伪代码就很简单了:

def dfs(rt):
    l = rt.left
    r = rt.right
    return l.val == r.val and dfs(l.left, r.right) and dfs(l.right, r.left)

根据伪代码不难写出解法:

top Created with Sketch.