[Leetcode]101. Symmetric Tree

📄 Description

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

🔨 My Solution

use Stack with iterative approach

🔴 Variablesleft : nodes of the left partsright : nodes of the right parts

🔵 Rules

1) Conditions for Symmetric Tree
- If the both left and right node is None , its Symmetric.
- If the one of the left and right node is None , its not Symmetric.
- If the value is different, its not symmetirc. In other words, the value have to be same to be a symmetric tree.
2) How to check the child nodes : BFS Search
- pop the left element( pop(0) ) from the left and right .
- For the left node's child, append the left.left first and then left.right .
- For the right node's child, append the right.right first and then right.left .

Why is the order you add to queue different?

If you see the above picture, you will understand why.
For the child node(both left and right) popped off from the left should be put in order of left->right, and the child node(both left and right) popped off form the right should be put in order of right->left.

💻 My Submission

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
		'''
        left: left part nodes
        right: right part nodes
        '''
        
        left=[root.left]
        right=[root.right]
        
        while left and right:
            l_node=left.pop(0)
            r_node=right.pop(0)
			# if the both l_node and r_node is None, its symmetric
            if not l_node and not r_node:
                continue
            # if one of the two is None, its not symmetric
            if not l_node or not r_node:
                return False
            # if the value is different, its not symmetirc
            if l_node.val!=r_node.val:  
                return False
            # append the left child and right node
            left.append(l_node.left)
            left.append(l_node.right)
            right.append(r_node.right)
            right.append(r_node.left)    
        return True

🎈 Follow up

Could you solve it both recursively and iteratively?

Other Solution (1) Recursion

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        
        return self.recursion(root.left, root.right)

    def recursion(self, l_node,r_node):
        if l_node is None and r_node is None:
            return True
        if l_node is None or r_node is None:
            return False
        
        if l_node.val==r_node.val:  
            return self.recursion(l_node.left, r_node.right) and self.recursion(l_node.right, r_node.left)
        else:
            return False

References
https://leetcode.com/problems/symmetric-tree/
https://leetcode.com/problems/symmetric-tree/discuss/33050/Recursively-and-iteratively-solution-in-Python