101. 对称二叉树

发表于 更新于 分类于 ，

题目

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

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

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

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

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

思路

上回说到,遇到树的题目,往递归方面靠会比较合适,要判断这个二叉树是否对称,相当于递归判断每一个节点的左右节点的子节点是否成为镜像.

代码

先实现一个递归函数,用来判断一个树的左右两个节点是否镜像对称

1
2
3
4
5
6
7
8
9
10
11
12
public bool IsSymmetricTree(TreeNode p, TreeNode q)
{
    if (p != null && q == null || p == null && q != null)//如果左null右非null或者右null左非null,说明一定不是对称的.
    {
        return false;
    }
    else
    {
        return (p == null && q == null) || (p.val == q.val) && IsSymmetricTree(p.left, q.right) && IsSymmetricTree(p.right, q.left);
        //先判断是不是都为null,然后再判断左右两个值是否相等,再递归判断左右子节点.
    }
}
1
2
3
4
public bool IsSymmetric(TreeNode root)
{
    return IsSymmetricTree(root, root);
}