This article is participating in Python Theme Month. See the link for details

Topic describes

This is “JZ 58 symmetric binary tree” on “Niuke.com”, the difficulty is “difficult”.

Tag: “Finger Offer”, “binary tree”, “order traversal”, “iteration”, “recursion”

Description:

Implement a function to determine whether a binary tree is symmetric.

Note that a binary tree is defined to be symmetric if its mirror image is the same.

Example 1

Input: {8,6,6,5,7,7,5} return value: trueCopy the code

Example 2

Input: {8,6,9,5,7,7,5} return value: falseCopy the code

Requirements:

  • Time: 1 s

  • Space: 64 M

The basic idea

First of all, it should be clear that the “symmetry” defined by the title is for each layer, while considering empty nodes.

Therefore, if we use the normal traversal method to check, we need to have some representation of the empty node.

Local inspection (sequence traversal)

We use 0x3f3f3f3f as an invalid value and create a placeholder node emptyNode to refer to the emptyNode (emptynode. val = 0x3f3f3f3f).

A simple way to do this is to “check layer by layer” using “sequential traversal”, using emptyNode to refer to empty nodes, and ensuring that no children of emptyNode are recursed.

Specific practices are as follows:

  1. At the start, add the root node to the team.

  2. Remove the node from the queue and check whether the node is emptyNode to decide whether to continue to queue:

  • If the emptyNode node is not an emptyNode, the left and right sons are added to the team. If the emptyNode node is not an emptyNode, the left and right sons are added to the team.

  • If the emptyNode node is used, this command is ignored.

  1. Use “temporary list” to record the information of current layer and check whether the current layer meets the requirements of “symmetry” at the same time of the process;

  2. Loop the process and until the entire queue is empty.

Java code:

import java.util.*;
class Solution {
    int INF = 0x3f3f3f3f;
    TreeNode emptyNode = new TreeNode(INF);
    boolean isSymmetrical(TreeNode root) {
        if (root == null) return true;

        Deque<TreeNode> d = new ArrayDeque<>();
        d.add(root);
        while(! d.isEmpty()) {// Each loop expands the next layer and places it in the queue
            // At the same time, the layer node values are successively saved to the "temporary list"
            int size  = d.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode poll = d.pollFirst();
                if(! poll.equals(emptyNode)) { d.addLast(poll.left ! =null? poll.left : emptyNode); d.addLast(poll.right ! =null ? poll.right : emptyNode);
                }
                list.add(poll.val);
            }
            
            // After each layer is expanded, check whether the current layer meets the "symmetry" requirement
            if(! check(list))return false;
        }
        return true;
    }

    // Use "double Pointers" to check whether a layer meets the "symmetry" requirement
    boolean check(List<Integer> list) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            if(! list.get(l).equals(list.get(r)))return false;
            l++;
            r--;
        }
        return true; }}Copy the code

Python 3 code:

from collections import deque
from math import inf

class Solution:
    emptyNode = TreeNode(inf)
    def isSymmetrical(self, root) :
        if root is None:
            return True
        d = deque([])
        d.append(root)
        while d:
            # Each loop expands the next layer into a queue
            Add the layer node values to the "temporary list"
            size = len(d)
            lt = []
            while size > 0:
                poll = d.popleft()
                ifpoll ! = self.emptyNode: d.append(poll.leftif poll.left is not None else self.emptyNode)
                    d.append(poll.right if poll.right is not None else self.emptyNode)
                size -= 1
                lt.append(poll.val)
            After each layer is expanded, check if the current layer meets the "symmetry" requirement
            if not self.check(lt):
                return False
        return True
    
    def check(self, lt) :
        # Use "double Pointers" to check whether a layer meets the "symmetry" requirement
        l, r = 0.len(lt) - 1
        while l < r:
            iflt[l] ! = lt[r]:return False
            l += 1
            r -= 1
        return True
Copy the code
  • Time complexity: In the process of sequence traversal, each node can join the queue at most oncecheckEach layer is checked only once during symmetry checks. The complexity is order n.
  • Space complexity: O(n)

Global check (recursive)

In the “sequence traversal” solution, we use the “symmetry” definition to check each layer.

This is essentially multiple “local” checks using the “symmetric” definition.

In fact, we can also use the definition of “symmetry” to examine it at the “holistic” level.

How do we define whether two subtrees A and B are “symmetric”?

Two subtrees meet the “symmetry” requirement if and only if they meet the following requirements:

  1. The two sub-root nodes have the same values;

  2. The left and right subtrees of the two subtrees are symmetric respectively, including:

  • The left subtree of a is equal to the right subtree of B

  • The right subtree of a has the same value as the left subtree of B

Specifically, we can design a recursive function check to pass in the head nodes a and B of the two subtrees to be detected (for this Case, we can pass root to both). In a single query, there are the following obvious Base cases to determine whether the subtrees are “symmetric” :

  • Both a and B are empty nodes: it meets the requirements of “symmetry”;

  • If one node of A and B is empty, it does not meet the requirement of “symmetry”.

  • The value of A and B are not equal, which does not meet the requirement of “symmetry”;

In other cases, we check whether the left and right nodes of A and B are “symmetric”, i.e. call check(a.light, b.light) and check(a.light, b.light) recursively.

Java code:

class Solution {
    public boolean isSymmetrical(TreeNode root) {
        return check(root, root);
    }
    boolean check(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        if(a.val ! = b.val)return false;
        returncheck(a.left, b.right) && check(a.right, b.left); }}Copy the code

Python 3 code:

class Solution:
    def isSymmetrical(self, root) :
        return self.check(root, root)

    def check(self, a, b) :
        if a is None and b is None:
            return True
        elif a is None or b is None:
            return False
        ifa.val ! = b.val:return False
        return self.check(a.left, b.right) and self.check(a.right, b.left)

Copy the code
  • Time complexity: Each node is accessed only once. The complexity is order n.
  • Space complexity: Ignore the extra space overhead caused by recursion. The complexity is order one.

conclusion

The above two solutions are not only different in implementation, but also check the difference of “starting point” :

  • Solution 1: The method of “sequence traversal” is used to check “symmetry” with “layer” as the unit;

  • Solution two: the use of “recursion tree expansion”, with “sub-tree” as the unit of “symmetry” check.

When we think about it on a holistic level, we can often write much cleaner code with recursion than we normally do.

I suggest you deepen your understanding of the two different starting points of “part” and “whole”.

The last

This is the 58th article of our series of “Jian Finger Symposium”, which started on 2021/07/01.

This series will cover all of the classic and outdated topics in “Finger Offer”.

In the pursuit of “proof” & “thinking” at the same time, to provide the most concise code.

Welcome attention, make a friend (‘ ω · ´)