image

題目

給定一個(gè)二叉樹(shù)，檢查它是否是鏡像對(duì)稱(chēng)的。

image

解題思路

遞歸解法

根據(jù)樹(shù)型知識(shí)里描述的，如果使用遞歸解決這道題，我們需要先找到子問(wèn)題，再通過(guò)不斷的遞歸這個(gè)子問(wèn)題，最后因?yàn)橄拗茥l件而中止。
這道題的子問(wèn)題是什么呢，如果一顆樹(shù)是對(duì)稱(chēng)的，那么他的左右子樹(shù)肯定是對(duì)稱(chēng)的。得到這樣的代碼。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSYM(root.left,root.right);
    }
    
    public boolean isSYM(TreeNode left,TreeNode right){
        //對(duì)稱(chēng)條件
    }
    
}

image

我們?cè)趺磁袛嘁豢脴?shù)的左右子樹(shù)是不是對(duì)稱(chēng)的呢，看上面這顆樹(shù)，只要根節(jié)點(diǎn)1的左子樹(shù)2的左結(jié)點(diǎn)3等于右子樹(shù)2的右結(jié)點(diǎn)3，并且左子樹(shù)2的右子樹(shù)4等于右子樹(shù)的左子樹(shù)4。滿足這樣的條件就是對(duì)稱(chēng)的。同樣到下一層，就是第三層的3和3、4和4對(duì)比。這樣就得到了子問(wèn)題。得到如下遞歸代碼

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)){
            //左右結(jié)點(diǎn)單個(gè)為空，那么不是對(duì)稱(chēng)的
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        //上面的條件，左左和右右相等，左右和右左相等
        return isSYM(left.left,right.right) && isSYM(left.right,right.left);
    }
}

迭代解法

現(xiàn)在我們使用迭代解決這道題呢，我們可以BFS層序遍歷，遍歷每一層，如果每一層是對(duì)稱(chēng)的，那么就是對(duì)稱(chēng)的。
我們從隊(duì)列中取元素時(shí)，可以一對(duì)一對(duì)的取，這樣如果取出的兩個(gè)數(shù)不相等，那么就不是對(duì)稱(chēng)的。那就需要我們的隊(duì)列里是1223344這樣排列。我們需要對(duì)稱(chēng)的放在一起，怎么實(shí)現(xiàn)呢，只要取出的成對(duì)元素中，先放第一個(gè)的左結(jié)點(diǎn)和第二個(gè)的右結(jié)點(diǎn)，接著放第一個(gè)的右結(jié)點(diǎn)和第二個(gè)的左結(jié)點(diǎn)。

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();
            //判斷兩個(gè)結(jié)點(diǎn)是否對(duì)稱(chēng)
            if(one == null || two==null){
                if(!(one == null && two == null)){
                    return false;
                }
            }else{
                if(one.val!=two.val){
                    return false;
                }
                //放置兩個(gè)相鄰對(duì)稱(chēng)的結(jié)點(diǎn)
                s.add(one.left);
                s.add(two.right);
                s.add(one.right);
                s.add(two.left);
            }
        }
        return true;
    }