100.Same_Tree

python

# 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:
        if p is None or q is None:
            if p is None and q is None:
                return True
            else:
                return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and \ self.isSameTree(p.right, q.right)

can be simplified as

python

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q  # 必须都是 None
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

作者：灵茶山艾府
链接：https://leetcode.cn/problems/same-tree/solutions/2015056/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-empk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

The point is return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

对于递归而言，只需要考虑base cases 和中间的m+1逻辑就行了，正如数学归纳法(mathematical induction)只要考虑n=1时成立和 n = m => n = m + 1 时成立就行。对这里而言，只要左右子树当前节点的value相等，并且左子树相等，并且右子树相等，就能得出两个树相等。