检查二叉树是否对称的技术 [英] Techniques used in checking if a binary tree is symmetric

问题描述

给出一棵二叉树，检查它是否是其自身的镜像(即，围绕其中心对称).问题链接位于此处

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). Question link is here

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

但是其中一条评论提供了一种解决方案，该解决方案使用了一种称为空检查"的技术.我不明白为什么这样才能避免两次检查树?

But one of the comment provided a solution used a technique called 'Null check'. I can't understand why in this way can we avoid checking the tree twice?

这是他的C ++代码:

Here is his code in 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，我的代码也通过了所有测试用例！

I have also tried to modify it into python3 and my code also passed all test cases!

这是我的代码:

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

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

I have never met such kind of recursion before.

(1)为什么我们可以在helper函数本身中用不同的参数重新定义函数helper?

(1) Why we can redefine the function helper with different arguments in helper function itself?

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

(2) My intuition tells me that helper function will stop execution once it returns back to the root thus the tree won't be checked twice. But I don't know why.

推荐答案

def 语句实际上只是一个花哨的赋值语句.在 Solution.helper 中，您将定义一个名为 helper 的本地变量，该变量绑定到另一个函数.结果， Solution.helper 内部的所有引用以及名称为 helper 的本地函数都将解析为本地函数.

A def statement is really just a fancy assignment statement. In Solution.helper, you are defining a local variable named helper that is bound to another function. As a result, all references inside Solution.helper and the local function to the name helper resolve to the local function.

Solution.helper 不是递归函数；它不是递归函数.只有本地功能.您可以编写与

Solution.helper is not a recursive function; only the local function is. You could write the same thing (less confusingly but equivalently) as

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)

这篇关于检查二叉树是否对称的技术的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！