title: LeetCode-101-对称的树
tags:
- Java
- 算法
data: 2018-12-26 22:08:38
categories: "技术"
description: "LeetCode第100题：对称的树"

题目

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

例如，二叉树 [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

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

题目分析

二叉树对称，肯定需要比较两个支线的对称情况，所以需要一个双参数的方法进行递归

解题思路

1. 如果需要其中一个支线为null，另一个不为null说明非对称二叉树
2. 如果全部为null说明为对称二叉树
3. 全部不为null需要满足以下条件才可以证明两个支线对称
   • 左支线值等于右支线值
   • 左支线的左支线与右支线的右支线对称
   • 左支线的右支线与右支线的左支线对称

代码实现

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetric(root.left,root.right);
    }
    public boolean isSymmetric(TreeNode left,TreeNode right){
        // 全部为null，对称
        if(left == null && right == null){
            return true;
        }
        // 非全部为null且包含null，说明其中一个为null，不对称
        if(left == null || right == null){
            return false;
        }
        // 左边的值等于右边的值，且左边的左支线与右边的右支线对称，且左边的右支线与右边的左支线对称
        return left.val == right.val 
            && isSymmetric(left.left,right.right) 
            && isSymmetric(left.right,right.left);
    }
}

思维拓展

使用迭代的方式实现

代码

public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while (!q.isEmpty()){
            TreeNode p1 = q.poll();
            TreeNode p2 = q.poll();
            if(p1 == null && p2 == null){
                continue;
            }
            if(p1 == null || p2 == null){
                return false;
            }
            if(p1.val != p2.val){
                return false;
            }
            q.add(p1.left);
            q.add(p2.right);
            q.add(p1.right);
            q.add(p2.left);
        }
        return true;
    }

分析

使用队列的方式进行依次进行比较按照，难点在于使用队列，非科班出身，工作中很少用到这个，已经忘记该如何使用了

总结

本节遇坑，一定要审题，对称指的是完全对称，不是其中一个支线单独对称

本节难点在于对称的要求是

左支线的值等于右支线的值且左支线的左支线与右支线的右支线对称且左支线的右支线与右支线的左支线对称