題⽬描述

請實現⼀個函數，⽤來判斷⼀棵⼆叉樹是不是對稱的。注意，如果⼀個⼆叉樹同此⼆叉樹的鏡像是同樣
的，定義其為對稱的。

例如：下⾯這棵⼆叉樹是對稱的

下⾯這個就不是對稱的：

示例1

輸⼊：{8,6,6,5,7,7,5}
返回值：true

示例2：

輸⼊：{8,6,9,5,7,7,5}
返回值：false

思路及解答

遞歸

遞歸，先判斷根節點是否為空，不為空則判斷左右⼦樹是不是對稱。

如果左右⼦樹都為空，則返回 true ，如果有⼀個為空，則返回 false ，如果兩個都不為空的時候，除了對⽐左右兩個節點的值，還需要遞歸，對⽐左⼦樹的左⼦樹和右⼦樹的右⼦樹是否相等，左⼦樹的右⼦樹和右⼦樹的左⼦樹是否相等。

public class Solution {
    public boolean jude(TreeNode left, TreeNode right) {
        // 如果左右兩個都為空，則對稱
        if (left == null && right == null) {
        	return true;
        } else if (left == null || right == null) {
            // 如果左右兩個有⼀個為空，那麼就不對稱
            return false;
        }
        
        // 都不為空的情況，需要判斷兩個的值，是不是相等
        if (left.val != right.val) {
        	return false;
        } else {
            // 遞歸判斷，左⼦樹的左⼦樹和右⼦樹的右⼦樹，左⼦樹的右⼦樹和右⼦樹的左⼦樹
            return jude(left.left, right.right) && jude(left.right, right.left);
        }
    }
    
    public boolean isSymmetrical(TreeNode pRoot) {
        // 判斷根節點是否為空，如果不為空則判斷左右⼦樹
        return pRoot==null || jude(pRoot.left, pRoot.right);
    }
}

• 時間複雜度：O(n)
• 空間複雜度：O(n),最壞情況下，⼆叉樹退化為鏈表

迭代

是藉助兩個隊列，按照層次，⼀個是按照從左到右添加元素，另外⼀個隊列
是按照從右到左添加元素，挨個取出來，進⾏對⽐，不等則説明不對稱，如果相等，則再把其左右⼦樹
分別按照不同的順序添加到隊列中。代碼如下

public class Solution {
    /**
    * 迭代法
     * 使用雙端隊列，相當於兩個棧
     */
    public boolean isSymmetric2(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.pollFirst();
            TreeNode rightNode = deque.pollLast();
            if (leftNode == null && rightNode == null) {
                continue;
            }

            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            deque.offerFirst(leftNode.left);
            deque.offerFirst(leftNode.right);
            deque.offerLast(rightNode.right);
            deque.offerLast(rightNode.left);
        }
        return true;
    }

    /**
     * 迭代法
     * 使用普通隊列
     */
    public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }

            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 這裏順序與使用Deque不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }
}

• 空間複雜度為 O(n)
• 時間複雜度為 O(n) ,每個節點只會⼊隊出隊⼀次。