Symmetric Tree

发表于   |   分类于 ，

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

描述

判断一棵树是否是镜面反射，主要看其是否中心对称

分析

将一棵树翻转，然后判断两棵树是否相等

代码

递归：

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {

        return isMirror(root, root);
    }

    private boolean isMirror(TreeNode x, TreeNode y) {

        if (x == null && y == null) {
            return true;
        }

        if (x == null || y == null) {
            return false;
        }

        return (x.val == y.val) && isMirror(x.right, y.left) && isMirror(x.left, y.right);
    }
}

非递归：

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
public class Solution {
    public boolean isSymmetric(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        queue.add(root);

        while (!queue.isEmpty()) {

            TreeNode x = queue.poll();
            TreeNode y = queue.poll();

            if (x == null && y == null) {
                continue;
            }

            if (x == null || y == null) {
                return false;
            }

            if (x.val != y.val) {
                return false;
            }

            queue.add(x.left);
            queue.add(y.right);
            queue.add(x.right);
            queue.add(y.left);
        }

        return true;
    }
}