CODEWITHSUNDEEP
pythonc++algorithmdata-structuresbinary-tree
Tian
Tian

Reputation: 15

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

The recursion method need to traverse the tree twice.

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?

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

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

Here is my code:

# 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) Why we can redefine the function helper with different arguments in helper function itself?

(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.

Upvotes: 0

Views: 377

Answers (2)

Ameer Jewdaki
Ameer Jewdaki

Reputation: 1798

The role of function isSymmetric(TreeNode* root is pretty simple. First, it returns true if the tree is empty, and if it's not, it checks if its left child is a mirror of its right child, which happens in the isSymmetric(TreeNode* t1, TreeNode* t2). So let's try to understand how the second function works. It is essentially designed to take two trees and check if they are mirrors of each other. How? First, it does the obvious checks. If one is null and the other is not, it returns false, and if both are null it returns true. The interesting part happens when both are potentially trees. It suffices that the left child of one is the mirror of the right child of the other and vice versa. You can draw a tree to see why this is the case. A schema should be self-explanatory.

Upvotes: 0

chepner
chepner

Reputation: 531125

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

Upvotes: 2

Related Questions