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

Question

给定一棵二叉树，检查它是否是自身的镜像（即围绕其中心对称）。问题 link 是 here

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

这是他的 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) 我的直觉告诉我辅助函数一旦 returns 回到根目录就会停止执行，因此树不会被检查两次。但是不知道为什么。

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的作用很简单。首先，它 returns true 如果树是空的，如果不是，它检查它的左 child 是否是它右 child 的镜像，这发生在isSymmetric(TreeNode* t1, TreeNode* t2)。因此，让我们尝试了解第二个功能的工作原理。它本质上是设计用来获取两棵树并检查它们是否是彼此的镜像。如何？首先，它进行明显的检查。如果一个是 null 而另一个不是，则 returns false，如果两者都是 null，则 returns true。当两者都可能是树时，有趣的部分就会发生。一个人的左边 child 是另一个人右边 child 的镜像就足够了，反之亦然。你可以画一棵树看看为什么会这样。架构应为 self-explanatory。

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

Techniques used in checking if a binary tree is symmetric

c++

python

algorithm

binary-tree

data-structures