Shulou(Shulou.com)06/01 Report--

How to analyze the symmetric binary tree in python? aiming at this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

Symmetric binary tree problem

Given a binary tree, check whether it is mirror symmetric.

For example, a binary tree [1, 2, 2, 3, 3, 4, 4, and 3] is symmetrical.

one

/\

2 2

/ /

3 4 4 3

But the following one is not mirror symmetrical:

one

/\

2 2

\\

3 3

Source: LeetCode link: https://leetcode-cn.com/problems/symmetric-tree/submissions/

# Definition for a binary tree node.

# class TreeNode (object):

# def _ _ init__ (self, x):

# self.val = x

# self.left = None

# self.right = None

Class Solution (object):

Def isSymmetric (self, root):

"

: type root: TreeNode

: rtype: bool

"

Error code

To determine whether the binary tree is symmetrical, let's first see if the following code is correct and what function it implements.

First of all, let's look at the recursive basis, which can be divided into three situations:

If there is no root, it is an empty tree. If True is returned, there is no left or right subtree. If True is returned, the left and right child nodes val are not equal. False is returned.

The recursive equation is as follows, judging that the left and right subtrees are symmetrical.

Self.isSymmetric (root.left) and self.isSymmetric (root.right)

Def isSymmetric (self, root):

"

: type root: TreeNode

: rtype: bool

"

If not root:

Return True

If not root.left and not root.right:

Return True

Return root.left = = root.right and self.isSymmetric (root.left) and self.isSymmetric (root.right)

The above code thinks that the following binary tree is symmetrical:

This is obviously different from the symmetric binary tree required by the topic, so that it is a true symmetric binary tree:

Correct code

The reason for the error code is that there is a problem with the recursive equation. Please take a look at the following picture:

Therefore, the correct recursive equation is obtained:

Sub (left.left,right.right) and sub (left.right,right.left)

Complete code:

Class Solution (object):

Def isSymmetric (self, root):

If not root:

Return True

Def sub (left,right):

# No left and right, return True

If not left and not right:

Return True

# No left or right, return False

If not left or not right:

Return False

Return left.val = = right.val and sub (left.left,right.right) and sub (left.right,right.left)

Return sub (root.left,root.right) on how to analyze the symmetric binary tree in the python question is shared here, I hope the above content can be of some help to you, if you still have a lot of doubts to solve, you can follow the industry information channel for more related knowledge.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.