Solve the problem iteratively by stack


  • 1
    public class Solution {
        public boolean isSymmetric(TreeNode root) {
            if(root ==  null){
    			return true;
    		}
    		if(root.left == null && root.right == null){
    			return true;
    		}
    		if(root.left == null || root.right == null){
    			return false;
    		}
    		
    		Stack<TreeNode> stk1 = new Stack<TreeNode>();
    		Stack<TreeNode> stk2 = new Stack<TreeNode>();
    		
    		stk1.push(root.left);
    		stk2.push(root.right);
    		
    		while(!stk1.isEmpty() && !stk2.isEmpty()){
    			TreeNode tn1 = stk1.pop();
    			TreeNode tn2 = stk2.pop();
    			//same val
    			if(tn1.val != tn2.val){
    				return false;
    			}
    			//same structure
    			if(tn1.left == null && tn2.right != null)
    				return false;
    			else if(tn1.left != null && tn2.right == null){
    				return false;
    			}else if (tn1.right == null && tn2.left != null) {
    				return false;
    			}else if(tn1.right != null && tn2.left == null){
    				return false;
    			}
    			
    			if(tn1.left != null && tn2.right != null){
    				stk1.push(tn1.left);
    				stk2.push(tn2.right);
    			}
    			
    			if(tn1.right != null && tn2.left != null ){
    				stk1.push(tn1.right);
    				stk2.push(tn2.left);
    			}
    		}
    		return true;
    		
        }
    }

Log in to reply
 

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