LeetCode二叉树专题 (3) 对称二叉树

image

题目

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

image

解题思路

递归解法

根据树型知识里描述的，如果使用递归解决这道题，我们需要先找到子问题，再通过不断的递归这个子问题，最后因为限制条件而中止。
这道题的子问题是什么呢，如果一颗树是对称的，那么他的左右子树肯定是对称的。得到这样的代码。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSYM(root.left,root.right);
    }
    
    public boolean isSYM(TreeNode left,TreeNode right){
        //对称条件
    }
    
}

image

我们怎么判断一棵树的左右子树是不是对称的呢，看上面这颗树，只要根节点1的左子树2的左结点3等于右子树2的右结点3，并且左子树2的右子树4等于右子树的左子树4。满足这样的条件就是对称的。同样到下一层，就是第三层的3和3、4和4对比。这样就得到了子问题。得到如下递归代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
         if(root == null){
            return true;
        }
        return isSYM(root.left,root.right);
    }
    
    public boolean isSYM(TreeNode left,TreeNode right){
        if(!(left==null && right==null) && (left==null||right==null)){
            //左右结点单个为空，那么不是对称的
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        //上面的条件，左左和右右相等，左右和右左相等
        return isSYM(left.left,right.right) && isSYM(left.right,right.left);
    }
}

迭代解法

现在我们使用迭代解决这道题呢，我们可以BFS层序遍历，遍历每一层，如果每一层是对称的，那么就是对称的。
我们从队列中取元素时，可以一对一对的取，这样如果取出的两个数不相等，那么就不是对称的。那就需要我们的队列里是1223344这样排列。我们需要对称的放在一起，怎么实现呢，只要取出的成对元素中，先放第一个的左结点和第二个的右结点，接着放第一个的右结点和第二个的左结点。

public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        //迭代
        LinkedList<TreeNode> s = new LinkedList<>();
        s.add(root.left);
        s.add(root.right);
        while(!s.isEmpty()){
            TreeNode one = s.poll();
            TreeNode two = s.poll();
            //判断两个结点是否对称
            if(one == null || two==null){
                if(!(one == null && two == null)){
                    return false;
                }
            }else{
                if(one.val!=two.val){
                    return false;
                }
                //放置两个相邻对称的结点
                s.add(one.left);
                s.add(two.right);
                s.add(one.right);
                s.add(two.left);
            }
        }
        return true;
    }