Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

describe

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
Copy the code

Example 2:

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

Note:

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100
Copy the code

parsing

A binary tree is given to determine whether the tree is symmetric according to the midline. At the beginning, I had a narrow mind. I thought that the tree itself was recursive, but I found it difficult. Finally, I saw daishen’s solution, which was clear and easy.

The idea is simple. We define a recursive function called Left and right, which respectively represent the root nodes of two trees. In the symmetric function, we pass two identical root nodes to operate two identical trees. Check whether the value of left is equal to the value of right. If the value is equal, continue to recursively symmetric(left. Left, right. Right) and symmetric(left. If not, return False.

answer

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def symmetric(left, right):
            if not left and not right: return True
            if left and right and left.val == right.val:
                return symmetric(left.left, right.right) and symmetric(left.right, right.left)
            return False
        return symmetric(root, root)
        	      
		
Copy the code

The results

Given in the Python online submissions for Symmetric Tree. Memory Usage: Given in the Python online submissions for Symmetric Tree.Copy the code

parsing

Of course, you can also use the stack to iterate over the nodes in the tree for comparison.

answer

class TreeNode(object): def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ if not root: return True stack = [(root.left, root.right)] while stack: l, r = stack.pop() if not l and not r: continue if not l or not r or (l.val ! = r.val): return False stack.append((l.left, r.right)) stack.append((l.right, r.left)) return TrueCopy the code

The results

Given in the Python online submissions for Symmetric Tree. Memory Usage: 10 ms Given in the Python online submissions for Symmetric Tree.Copy the code

Original link: leetcode.com/problems/sy…

Your support is my biggest motivation