用于检查二叉树是否对称的技术

Question

给定一个二叉树，检查它是否是自身的镜像(即围绕其中心对称(。问题链接在这里

递归方法需要遍历树两次。

但是其中一条评论提供了使用称为"空检查"的技术的解决方案。我不明白为什么这样我们可以避免两次检查树？

以下是他在C++的代码：

bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return isSymmetric(root->left, root->right);
    }
    bool isSymmetric(TreeNode* t1, TreeNode* t2){
        if (!t1 && !t2) return true;
        if (!t1 || !t2) return false;
        return t1->val == t2->val
            && isSymmetric(t1->left, t2->right)
            && isSymmetric(t1->right, t2->left);
    }

我也尝试将其修改为 python3，我的代码也通过了所有测试用例！

这是我的代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def isSymmetric(self, root):
        return self.helper(root)
    def helper(self,root):
        if root is None:
            return True
        #why we can redefine the helper here?
        def helper(left,right):
            if left is None and right is None:
                return True
            if left is None or right is None:
                return False
            return left.val==right.val and helper(left.left,right.right) and helper(left.right,right.left)
        return helper(root.left,root.right)

我以前从未遇到过这种递归。

(1(为什么我们可以在辅助函数本身中用不同的参数重新定义函数助手？

(2(我的直觉告诉我，辅助函数一旦返回到根，就会停止执行，因此树不会被检查两次。但我不知道为什么。

Answer 1

def语句实际上只是一个花哨的赋值语句。在Solution.helper中，你定义了一个名为helper的局部变量，它绑定到另一个函数。因此，Solution.helper 中的所有引用和本地函数对名称的引用helper解析为本地函数。

Solution.helper不是递归函数;只有局部函数才是。你可以写同样的东西(不那么令人困惑，但等效地(作为

class Solution:
    def isSymmetric(self, root):
        return self.helper(root)
    def helper(self,root):
        if root is None:
            return True
        def helper2(left,right):
            if left is None and right is None:
                return True
            if left is None or right is None:
                return False
            return left.val==right.val and helper2(left.left,right.right) and helper2(left.right,right.left)
        return helper2(root.left,root.right)

Answer 2

函数isSymmetric(TreeNode* root的作用非常简单。首先，如果树为空，它返回true，如果不是，则检查其左子项是否是其右子项的镜像，这发生在isSymmetric(TreeNode* t1, TreeNode* t2)中。因此，让我们尝试了解第二个函数的工作原理。它本质上旨在拍摄两棵树并检查它们是否是彼此的镜子。如何？首先，它进行明显的检查。如果一个是null而另一个不是，则返回false，如果两者都null则返回true。当两者都可能是树时，就会发生有趣的部分。一个人的左孩子是另一个人的右孩子的镜子就足够了，反之亦然。你可以画一棵树，看看为什么会这样。架构应该是不言自明的。