Recursive and iterative solutions


  • 0
    //recursive
    public boolean isSymmetric(TreeNode root) {
            if(root==null) return true;
            return isEqual(root.left,root.right);
        }
    	
    public boolean isEqual(TreeNode left,TreeNode right){
    	if(left==null||right==null) return left==right;
    	if(left.val!=right.val) return false;
    	return isEqual(left.left,right.right)&&isEqual(left.right,right.left);
    }
    
    //iteration
    public boolean isSymmetric(TreeNode root) {
            if(root==null) return true;
            if(root.left==null||root.right==null) return root.left==root.right;
            Queue<TreeNode> queue = new LinkedList();
            queue.offer(root.left);
            queue.offer(root.right);
            while(queue.size()>0){
            	//get nodes in pairs
            	TreeNode node1 = queue.poll();
            	TreeNode node2 = queue.poll();
            	if(node1.val!=node2.val) return false;
            	//deal null condition
            	if(node1.left==null||node2.right==null){
            		if(node1.left!=node2.right) return false;
            	};
            	if(node1.right==null||node2.left==null) {
            		if(node1.right!=node2.left) return false;
            	}
            	//add nodes in pairs
            	if(node1.left!=null) queue.offer(node1.left);
            	if(node2.right!=null) queue.offer(node2.right);
            	if(node1.right!=null) queue.offer(node1.right);
            	if(node2.left!=null) queue.offer(node2.left);
            }
            return true;
        }

  • 0
    X

    @NaLanZiYi " Queue<TreeNode> queue = new LinkedList();" does that even work? Isn't Queue an interface in java?


  • 0

    @xTEddie This is polymorphism in java ,since LinkedList has implemented Queue, you can use a Queue variable which actually hold a child type like LinkedList


  • 0
    X

    @NaLanZiYi it makes sense! thanks for the info! Does the instance only inherit methods from the queue interface itself? can methods of linkedlist be called?


  • 0

    @xTEddie In this case,Queue<TreeNode> queue = new LinkedList(),variable queue can only call function inherited from Queue interface , for queue is declared as a Queue type, it can not call a method not declared in Queue.


Log in to reply
 

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