java如果我想在ArrayQue中提供null，我该怎么做

Question

首先，别误会我。我知道如果指定的元素在ArrayDeque.offer()中为空，则会有NullPointerException。我的意思是，如果我想提供一些东西，是否有一个可行的替代方案在语法上是有效的，这表明它本身是无效的？ 情况如下：

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

A:

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;
    }
}

但这其中有一些问题：

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

这就是我的问题

Answer 1

简单但不太好的解决方案：

• 使用ArrayDeque<Optional<MyClass>>和MyClass作为你的类。然后您可以添加一个空的可选项
• 您还可以为此使用任何其他包装器类，并将包含的元素设置为null

更好的解决方案：

但为了更好地解决你的问题，通常我建议你使用特殊元素，定义为常数，如下所示：

static public final MyClass STOP_INDICATOR = new MyClass(); 如果需要更多信息，MyClass可能会安装一些特殊的CTOR

如果随后检索并检查它，甚至可以使用标识检查a == b，而不必使用a.equals(b)，因为它是一个常量

Answer 2

谢谢你激励我！这是我的最终版本算法：

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;
    }
}

然而，对于这个问题来说，它不是一个好的算法，因为它需要大量额外的堆栈内存空间

Answer 3

我觉得你应该用Null Object Pattern。您可以将任何对象（最好使其不可变）定义为null值，并在任何地方使用它，而不是null。例如，如果你使用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");
}

另一种解决方案是，您可以在Deque中使用Optional而不是TreeNode：

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");
}