Comparing whether two trees are same or not?-CodePudding

This is the question https://leetcode.com/problems/same-tree/

Question: 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.

I have used Python for solving this problem This is my approach. Could you tell why it failed the given test case? https://leetcode.com/submissions/detail/661792014/

My approach:

#Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        a = m = p
        b = n = q
        if p is None and q is None:
            return True
        elif p is None or q is None:
            return False
        
        while a:
            if a.val != b.val:
                return False
            
            if a.left:
                a = a.left
                if b.left:
                    b = b.left
                else:
                    return False
            else:
                if b.left:
                    return False
                else:
                    break
                
            
        while m:
            if m.val != n.val:
                return False

            if m.right:
                m = m.right
                if n.right:
                    n = n.right
                else:
                    return False
            else:
                if n.right:
                    return False
                else:
                    break

        return True

CodePudding user response：

The problem is that in your while loop, m will go all the way down via the same-side child (first loop: left, second loop right), but when it reaches the end, it will not backtrack and then look at all the opposite sided subtrees it had skipped along the way.

For example, take this tree:

            4
          /   \
         2     6
        / \   / \
       1   3 5   7

The first loop will check the left side (i.e. 4, 2 and 1), and the second loop will check the right side (i.e. 4, 6, 7), but there is no provision to go down the tree in a zig-zag way, so the nodes with 3 and 5 are never checked.

What you need here, is recursion. Solve the problem recursively for the left subtree and again recursively for the right subtree. If either returns that there is a difference, stop, and return False. If both calls give a positive result, and also the current node is equal, return True.

The solution (spoiler):

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: return bool(not p and not q or p and q and p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))