Iterative solution in Java with queue and an array


  • 0
    Q

    The solution is to use a queue to store tree nodes per level. Nodes in the next level will be counted and added to the end of the queue. Values of each node at the same level will be meanwhile added to an Integer array, with null value representing null child. Check array per level and determine if nodes are symmetric at the current level.

             public boolean isSymmetric(TreeNode root) {
    		if (root == null) {
    			return true;
    		}	
    	
    		LinkedList<TreeNode> queue = new LinkedList<>();
    		List<Integer> levelTreeNodes = new ArrayList<>();
    		
    		queue.add(root);
    		TreeNode current = root;
    		int currentLevelCount = 1;
    		int nextLevelCount = 0;
    		
    		while (!queue.isEmpty()) {
    			while (currentLevelCount-- > 0) {
    				current = queue.pollFirst();
    				if (current.left == null) {
    					levelTreeNodes.add(null);
    				} else {
    					levelTreeNodes.add(current.left.val);
    					queue.add(current.left);
    					nextLevelCount++;
    				}
    				
    				if (current.right == null) {
    					levelTreeNodes.add(null);
    				} else {
    					levelTreeNodes.add(current.right.val);
    					queue.add(current.right);
    					nextLevelCount++;
    				}
    			} 
    			currentLevelCount = nextLevelCount;
    			nextLevelCount = 0;
    			if (!isCurrentLevelSymmetric(levelTreeNodes)) {
    				return false;
    			}
    			levelTreeNodes.clear();
    		}
    		return true;
    	}
    	
    	private boolean isCurrentLevelSymmetric(List<Integer> levelTreeNodes) {
    		int size = levelTreeNodes.size();
    		for (int i = 0; i <= size / 2 - 1; i++) {
    			if (levelTreeNodes.get(i) != levelTreeNodes.get(size - 1 - i)) {
    				return false;
    			}
    		}
    		return true;
    	}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.