比较两棵树是否相同？

Question

这就是问题 https://leetcode.com/problems/same-tree/

问题：给定两棵二叉树 p 和 q 的根，编写一个函数来检查它们是否相同。两棵二叉树如果结构相同，节点值相同，则认为是相同的。

我已经用 Python 解决了这个问题这是我的方法。你能说出为什么它没有通过给定的测试用例吗？ https://leetcode.com/submissions/detail/661792014/

我的做法：

#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

Answer 1

问题在于，在您的 while 循环中，m 将通过 same-side 子循环（第一个循环：left，第二个循环 right), 但是当它到达终点时，它不会回溯然后查看它沿途跳过的所有相对边的子树。

例如，以这棵树为例：

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

第一个循环将检查左侧（即 4、2 和 1），第二个循环将检查右侧（即 4、6、7），但没有规定向下树以 zig-zag 方式，因此永远不会检查具有 3 和 5 的节点。

这里你需要的是递归。对左子树递归求解，对右子树递归求解。如果 return 中的任一个存在差异，则停止，并且 return 为假。如果两个调用都给出肯定的结果，并且当前节点相等，return True.

解决方案（剧透）：

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))

比较两棵树是否相同？

Comparing whether two trees are same or not?

tree

binary-tree

python-3.x