Java Iterative solution with comments


  • 0
    S

    public boolean isSameTree(TreeNode p, TreeNode q) {

        // Base condition for null values
        if(p == null && q == null) {
            return true;    // Both are null
        } else if (p == null || q == null) {
            return false;   // Only one of them is null
        }
        
        // Initialize Stacks
        Stack<TreeNode> pStack = new Stack<>();
        Stack<TreeNode> qStack = new Stack<>();
        
        // Add roots of p and q
        pStack.push(p);
        qStack.push(q);
        
        while (!pStack.isEmpty() || !qStack.isEmpty()) {
            TreeNode currP = pStack.pop();
            TreeNode currQ = qStack.pop();
            
            // Check if values are same
            if(currP.val != currQ.val) {
                return false;
            }
            
            // if both p & q have left elements add to stack
            if(currP.left != null && currQ.left != null) {
                pStack.push(currP.left);
                qStack.push(currQ.left);
            } else if (currP.left != null || currQ.left != null) { 
                return false; // If only one, p or q has left element
            }
            
            // if both p & q have left elements add to stack
            if(currP.right != null && currQ.right != null) {
                pStack.push(currP.right);
                qStack.push(currQ.right);
            } else if (currP.right != null || currQ.right != null) {
                return false; // If only one, p or q has right element
            }
        }
        
        // All elements are same
        return true;
    }

Log in to reply
 

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