剑指 Offer 28. 对称的二叉树

剑指 Offer 28. 对称的二叉树

递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return help(root.left, root.right);
    }

    boolean help(TreeNode left, TreeNode right){
        if(left == null && right == null) return true;
        if(left == null || right == null) return false;
        
        if(left.val != right.val) return false;

        return help(left.left, right.right) && help(left.right, right.left);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

迭代

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;

        Deque<TreeNode> leftQueue = new LinkedList<>();
        Deque<TreeNode> rightQueue = new LinkedList<>();
        leftQueue.offer(root);
        rightQueue.offer(root);

        while(!leftQueue.isEmpty() && !rightQueue.isEmpty()){
            TreeNode leftNode = leftQueue.poll();
            TreeNode rightNode = rightQueue.poll();

            if(leftNode == null && rightNode == null) continue;
            if(leftNode == null || rightNode == null) return false;
            if(leftNode.val != rightNode.val) return false;

            leftQueue.offer(leftNode.left);
            leftQueue.offer(leftNode.right);
            rightQueue.offer(rightNode.right);
            rightQueue.offer(rightNode.left);
        }

        return leftQueue.isEmpty() && rightQueue.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26