My non-recursive method


  • 51
    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

  • 19
    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!

  • 0
    X

    I tried to use stack but forgot to check the size, it is a really good idea!


  • 0
    S

    I use two queues for BFS and also get it right.

    Anyone plz correct me if I'm wrong. Stack is used for DFS, and queue is used for BFS. Both can be used for graph search.

    In this case of comparing whether two trees are the same, is there any difference between using BFS and DFS?

    Any discussion is appreciated! Thanks.


Log in to reply
 

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