My non-recursive method


  • 50
    S

    the idea is to use stack for preorder traverse

    public boolean isSameTree(TreeNode p, TreeNode q) {
    	     Stack<TreeNode> stack_p = new Stack <> ();       
    	     Stack<TreeNode> stack_q = new Stack <> ();
    	     if (p != null) stack_p.push( p ) ;
    	     if (q != null) stack_q.push( q ) ;
    	     while (!stack_p.isEmpty() && !stack_q.isEmpty()) {
    	    	 TreeNode pn = stack_p.pop() ;
    	    	 TreeNode qn = stack_q.pop() ;	    	
    	    	 if (pn.val != qn.val) return false ;
    	    	 if (pn.right != null) stack_p.push(pn.right) ;
    	    	 if (qn.right != null) stack_q.push(qn.right) ;
    	    	 if (stack_p.size() != stack_q.size()) return false ;
    	    	 if (pn.left != null) stack_p.push(pn.left) ;	    	 	    	 
    	    	 if (qn.left != null) stack_q.push(qn.left) ;
    	    	 if (stack_p.size() != stack_q.size()) return false ;
    	     }		     
    	     return stack_p.size() == stack_q.size() ;	 
    	 }

  • 3
    Y

    It is good!!!!!!!!!!!!!!Solution!!!!!!!!!!!!!!!!!!


  • 3
    J

    Actually, one stack is enough to solve this.


  • 0
    K

    There is no "size" method for Stack in java.


  • 0
    V

  • 18
    J

    actually, one stack is ok to solve this, but still thanks you give me idea to use list to solve this problem.

        stack = [(p,q)]
        while stack :
            x,y = stack.pop()
            if x == None and y ==None:
                continue
            if x == None or y == None:
                return False
            if x.val == y.val:
                stack.append((x.left,y.left))
                stack.append((x.right,y.right))
            else:
                return False
        return True

  • 0
    J

    i have just started learning JAVA, and have some interest in solving algorithms on leetcode.
    For this problem, I have written a code using your concept (almost the same), but there is always runtime error: Time Limit Exceeded with the last input: [1,null,1]
    I dont understand, can someone help me please?
    Thanks!!

    //Time Limit Exceeded ?
    public class Solution{
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p ==null && q == null) return true;
            if (p ==null || q == null) return false;
        
            else{
                Stack <TreeNode> stackp = new Stack<>();
                Stack <TreeNode> stackq = new Stack<>();
                stackp.push(p);
                stackq.push(q);
                while (!stackp.isEmpty() && !stackq.isEmpty()){
                    TreeNode nodep = stackp.pop();
                    TreeNode nodeq = stackq.pop();
                    if (nodep.val != nodeq.val) return false;
            
                    if (p.left != null) stackp.push(p.left);
                    if (q.left != null) stackq.push(q.left);
                    if (stackp.size() != stackq.size()) return false;
                    if (p.right != null) stackp.push(p.right);
                    if (q.right != null) stackq.push(q.right);
                    if (stackp.size() != stackq.size()) return false;
                }
            return stackp.size() == stackq.size();
    
            }
        }
    }

  • 0
    S

    hi!you have declare two variables :nodep and nodeq,and you should use them in the folowing codes instead of p and q.


  • 1
    K

    there is, Stack inherits size() method from Vector


  • 2
    I
    bool isSameTree(TreeNode* p, TreeNode* q) {
            stack<TreeNode*> stk1;
            stack<TreeNode*> stk2;
            
            stk1.push(p);
            stk2.push(q);
            
            while(!stk1.empty() && !stk2.empty()){
                TreeNode* tmp1 = stk1.top();
                TreeNode* tmp2 = stk2.top();
                stk1.pop();
                stk2.pop();
                
                if(tmp1 && tmp2){
                    if(tmp1->val != tmp2->val)
                        return false;
                    stk1.push(tmp1->left);
                    stk1.push(tmp1->right);
                    stk2.push(tmp2->left);
                    stk2.push(tmp2->right);
                }
                if((tmp1 && !tmp2) || (!tmp1 && tmp2))
                    return false;
            }
            
            return stk1.empty() == stk2.empty();
        }

  • 0
    E

    @Juliaz in the while loop, use nodeP, nodeQ instead of p and q. You are dealing with the nodes just popped up from the stack, instead of the two roots as the arguments.


  • 0
    Y

    so clearly and directly ,nice work!!!


  • 0
    S

    Can simplify the iterative Python solution to <10 lines:

    def isSameTree(self, p, q):
        stk = [(p, q)]
        while stk:
            x, y = stk.pop()
            if not x or not y: 
                if x is y: continue
                return False
            if x.val != y.val: return False
            stk.extend([(x.left, y.left), (x.right, y.right)])
        return True
    

  • 0
    Y
    This post is deleted!

  • 0
    L

    @Juliaz I don't understand what you write about

     else{
    

  • 0
    L
    • A more complete and consistent set of LIFO stack operations is

    • provided by the {@link Deque} interface and its implementations, which
    • should be used in preference to this class.

  • 2
    B

    One queue is enough.

        public boolean isSameTree(TreeNode p, TreeNode q) {
            Deque<TreeNode> queue = new LinkedList<>();
            queue.addLast(p);
            queue.addLast(q);
            while (!queue.isEmpty()) {
                p = queue.removeFirst();
                q = queue.removeFirst();
                
                if (p == null && q == null) {
                    continue;
                } else if (p == null || q == null || p.val != q.val) {
                    return false;
                } else {
                    queue.addLast(p.left);
                    queue.addLast(q.left);
                    queue.addLast(p.right);
                    queue.addLast(q.right);
                }          
            }
            return true;
        }
    

    or

        public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            } 
            if (p == null || q == null || p.val != q.val) {
                return false;
            }        
            
            Deque<TreeNode> queue = new LinkedList<>();
            queue.addLast(p);
            queue.addLast(q);
            while (!queue.isEmpty()) {
                p = queue.removeFirst();
                q = queue.removeFirst();
                
                if (p.left == null && q.left == null) {
                } else if (p.left == null || q.left == null || p.left.val != q.left.val) {
                    return false;
                } else {
                    queue.addLast(p.left);
                    queue.addLast(q.left);
                }  
                
                if (p.right == null && q.right == null) {
                } else if (p.right == null || q.right == null || p.right.val != q.right.val) {
                    return false;
                } else {
                    queue.addLast(p.right);
                    queue.addLast(q.right);
                }
            }
            return true;
        }
    

  • 0
    B
    This post is deleted!

Log in to reply
 

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