101. Symmetric Tree

, ,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left != null && right != null) {
            return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
        } else {
            return left == null && right == null;
        }
    }
}

BFS

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
27
28
29
30
31
32
33
34
35
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>(); // 队列中含有空节点
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            TreeNode nodeA = queue.poll();
            TreeNode nodeB = queue.poll();

            if (nodeA == null && nodeB == null) {
                continue; // 注意此处是 continue 而不是 return true, 因为此时可能处理的某个节点的两个子节点
            }

            if (nodeA != null && nodeB != null) {
                if (nodeA.val == nodeB.val) {
                    queue.offer(nodeA.left);
                    queue.offer(nodeB.right);
                    queue.offer(nodeA.right);
                    queue.offer(nodeB.left);
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }

        return true;
    }
}

此题需要注意的是对称的定义，对称不仅仅要求左子节点的值与右子节点的值相等，而且需要左子节点的右子节点与右子节点的左子节点相等，且右子节点的左子节点与左子节点的右子节点相等。

References

101. Symmetric Tree
剑指 Offer 28. 对称的二叉树
动画演示+多种实现 101. 对称二叉树