If I want to offer a null into an ArrayDeque, how could I do it-CodePudding

Firstly, don't get me wrong. I know there will be NullPointerException if the specified element is null in the ArrayDeque.offer(). What I mean is that whether there is a viable alternative that is valid grammatically if I want offer something indicates itself is null into it? The case is below:

Q: Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its centre).
Constraints:
1.The number of nodes in the tree is in the range [1, 1000].
2.-100 <= Node.val <= 100

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        Deque<Integer> stack = new ArrayDeque<>();
        
        if (root != null) {
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
            
                for (int i = 0; i < size; i  ) {
                    TreeNode node = queue.poll();
                  
                    if (stack.isEmpty() || stack.peek() != node.val) {
                        stack.push(node.val);
                    } else { 
                        stack.pop();
                    }
                    if (node != null) {                     
                        queue.offer(node.left);
                        queue.offer(node.right);
                    }
                   
                }
                if (!stack.isEmpty()) {
                    return false;
                }
            }
        }

        return true;
    }
}

But there is something wrong in:

queue.offer(node.left);  // offer a null is valid
queue.offer(node.right);  // offer a null is valid

So that's my question.

CodePudding user response：

I think you should use Null Object Pattern. You can define any object (it's better to make it immutable) as null value and use it everywhere instead of null. E.g. if you use Jackson:

public static final TreeNode NULL = NullNode.getInstance();

Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(NULL);

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

    if(node == NULL)
        System.err.println("null object");
    else
        System.out.println("not null object");
}

Another solution, you can use Optional instead of TreeNode in the Deque:

Deque<Optional<TreeNode>> queue = new ArrayDeque<>();
queue.offer(Optional.empty());

while (!queue.isEmpty()) {
    Optional<TreeNode> optNode = queue.poll();

    if (optNode.isEmpty())
        System.err.println("null object");
    else
        System.out.println("not null object");
}

CodePudding user response：

Simple but not so good solution:

Use ArrayDeque<Optional<MyClass>> with MyClass being your class. Then you can add an empty Optional.
You could also use any other wrapper class for this, and set the contained element null.

Better solution:

But to solve your problem better, generally I'd suggest you have special elements, defined as constants, like so:

static public final MyClass STOP_INDICATOR = new MyClass(); and MyClass maybe fitted with some special CTOR if it needs more info.

If you then retrieve it and check it, you can even use the identity check a == b and don't have to use a.equals(b), because it's a constant.

CodePudding user response：

Thanks for your helps! This is my final-version-algorithm:

class Solution {
static final TreeNode NULL_TREENODE = new TreeNode(101);

public boolean isSymmetric(TreeNode root) {
    Deque<TreeNode> queue = new ArrayDeque<>();
    Deque<Integer> stack = new ArrayDeque<>();
    
    if (root != null) {
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i  ) {
                TreeNode node = queue.poll();
                if (node != root) {  
                   stack.push(node.val);
                } 
                if (node != NULL_TREENODE) {

                    if (node.left != null) {
                        queue.offer(node.left);
                    } 
                    if (node.left == null) {  
                        queue.offer(NULL_TREENODE);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                    if (node.right == null) {
                        queue.offer(NULL_TREENODE);
                    }
               }
            }
      
            while (!stack.isEmpty()) {
                if (stack.removeFirst() != stack.removeLast()) {
                    return false;
                }
            }
        }
    }

    return true;
}

}

However, it's not a good algorithm for this Q, cause it needs much extra memory space by the stack...