Simple iterative solution


  • 5
    public class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p == null && q == null){
    			return true;
    		}
    		//structure
    		if(p == null || q == null){
    			return false;
    		}
    		//val
    		if(p.val != q.val){
    			return false;
    		}
    		
    		Stack<TreeNode> stk1 = new Stack<TreeNode>();
    		Stack<TreeNode> stk2 = new Stack<TreeNode>();
    		stk1.push(p);
    		stk2.push(q);
    		
    		while( !stk1.isEmpty() && !stk2.isEmpty() ){
    			TreeNode tn1 = stk1.pop();
    			TreeNode tn2 = stk2.pop();
    			
    			if(tn1.val != tn2.val){
    				return false;
    			}
    			//structure different
    			if(tn1.left == null && tn2.left != null){
    				return false;
    			}else if (tn1.left != null && tn2.left == null){
    				return false;
    			}else if (tn1.right == null && tn2.right != null){
    				return false;
    			}else if (tn1.right != null && tn2.right == null) {
    				return false;
    			}
    			
    			if(tn1.left != null && tn2.left != null){
    				stk1.push(tn1.left);
    				stk2.push(tn2.left);
    			}
    			
    			if(tn1.right != null && tn2.right != null){
    				stk1.push(tn1.right);
    				stk2.push(tn2.right);
    			}
    		}
    		
    		return true;
            
        }
    }

Log in to reply
 

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