Topic describes

This is “JZ 58 Symmetric Binary Tree” on “Niuke.com”, difficulty is “difficult”.

Tag: “Sword Offer”, “Binary Tree”, “Sequential Traversal”, “Iteration”, “Recursion”

Description:

Implement a function that determines whether a binary tree is symmetric.

Note that if a binary tree is the same as the image of the binary tree, define it as symmetric.

Example 1

Enter {8,6,6,5,7,7,5} and return true

Example 2

Enter {8,6,9,5,7,7,5} and return false

Requirements:

  • Time: 1 s
  • Space: 64 M

The basic idea

First of all, it’s clear that the definition of “symmetry” is for each layer, taking into account empty nodes.

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

Local check (sequence traversal)

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

A simple approach is to “check level by level” using “sequential traversal”, using emptyNode to refer to empty nodes, and making sure not to recurse the corresponding children of emptyNode.

Specific practices are as follows:

  1. So at the beginning, we’re going torootNode queue entry;
  2. Remove the node from the queue and check whether the node isemptyNodeNode to decide whether to continue to join the team:
  • When notemptyNodeNode, enlist its left/right sons in the queue, if there is no left/right sons, then useemptyNodeInstead of joining the team;
  • whenemptyNodeNode, is ignored;
  1. During the process, the “temporary list” is used to record the information of the current layer and check whether the current layer meets the requirements of “symmetry”;
  2. Loop the flow and until the entire queue is empty.

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 (! Int size = d.size(); int size = d.size(); 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 to see if the layer that holds the current layer is "symmetric". check(list)) return false; } return true; } 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; }}
  • Time complexity: In the sequence traversal process, each node is queued at most once and at the same timecheckEach layer is checked only once during symmetry checking. Complexity of
  • Space complexity:

Global check (recursion)

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

This is essentially a number of “local” checks using the “symmetric” definition.

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

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

If and only if the two subtrees meet the following requirements, the “symmetry” requirement is met:

  1. The root node values of the two subtrees are the same;
  2. The left and right subtrees of the two subtrees are symmetric respectively, including:
  • aThe left subtree of a tree andbThe corresponding values of the right subtree of the tree are equal
  • aThe right subtree of a tree andbThe corresponding values of the left subtree of the tree are equal

To be specific, we can design a recursive function check, pass the head nodes of the two subtrees to be detected (for this Case, pass root), and there is an obvious Base Case for judging whether the subtree is “symmetric” in a single query:

  • a 和 bAll nodes are empty: they meet the requirements of “symmetry”;
  • a 和 bOne of the nodes is empty and does not meet the requirement of “symmetry”;
  • a 和 bValue is not equal, does not meet the “symmetry” requirements;

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

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;
        return check(a.left, b.right) && check(a.right, b.left);
    }
}
  • Time complexity: Each node is accessed only once. Complexity of
  • Space complexity:

conclusion

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

  • Solution 1: Use the method of “sequence traversal” to carry out “symmetry” check with “layer” as unit;
  • Solution 2: Use the method of “recursion tree expansion” to carry out “symmetry” check with “subtree” as unit.

When we think of it as a whole, we can often write much cleaner code with recursion than we would normally do.

It is recommended that you deepen your understanding of the two different starting points of “part” and “whole”.

The last

This is the 58th article in our “Sword Finger の Selection” series, which began on January 07/01, 2012.

This series will be “sword point Offer” in the classic but outdated topics are all told again.

While providing the pursuit of “proof” & “ideas”, it also provides the most concise code.

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