首页 > itarticle > [leetcode] problem 101 – symmetric tree

[leetcode] problem 101 – symmetric tree

admin 11月 13, 2020 0

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

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note

Bonus points if you could solve it both recursively and iteratively.

Recursive

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

private boolean isSymmetricHelper(TreeNode n1, TreeNode n2) {
    if (n1 == null && n2 == null)
        return true;
    else if (n1 == null || n2 == null || n1.val != n2.val)
        return false;
    
    return isSymmetricHelper(n1.left, n2.right) && isSymmetricHelper(n1.right, n2.left);
}

Iterative

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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 n1 = queue.poll();
        TreeNode n2 = queue.poll();

        if (n1 == null && n2 == null)
            continue;
        else if (n1 == null || n2 == null || n1.val != n2.val)
            return false;
        
        queue.offer(n1.left);
        queue.offer(n2.right);
        queue.offer(n1.right);
        queue.offer(n2.left);
    }

    return true;
}