Same Tree - rFronteddu/general_wiki GitHub Wiki

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Recursive

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // If both nodes are null, they are the same
        if (p == null && q == null) {
            return true;
        }
        // If one of the nodes is null but not the other, they are not the same
        if (p == null || q == null) {
            return false;
        }
        // Check if the current nodes' values are the same
        if (p.val != q.val) {
            return false;
        }
        // Recursively check the left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Iterative

class Solution {
    public boolean isSameTree (TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }

        
        Queue<TreeNode> pq = new LinkedList<>();
        Queue<TreeNode> qq = new LinkedList<>();
        pq.add(p);
        qq.add(q);
        
        while (!pq.isEmpty() && !qq.isEmpty()) {
            TreeNode a = pq.poll();
            TreeNode b = qq.poll();

            if (a.val != b.val) {
                return false;
            }

            if (a.left != null & b.left != null) {
                pq.add(a.left);
                qq.add(b.left);
            } else if (a.left != b.left) {
                return false;
            }
            if (a.right!= null & b.right!= null) {
                pq.add(a.right);
                qq.add(b.right);
            } else if (a.right!= b.right) {
                return false;
            }
        }

        return pq.isEmpty() && qq.isEmpty();
    }
}
⚠️ **GitHub.com Fallback** ⚠️