This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Symmetric binary trees (Question 101)

The title

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

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

    1
   / \
  2   2/ \ \3  4 4  3
Copy the code

But the following [1,2,2,null,3,null,3] is not mirror symmetric:

    1
   / \
  2   2
   \   \
   3    3
Copy the code

Advanced:

Can you solve this problem both recursively and iteratively?

link

Leetcode-cn.com/problems/sy…

explain

This one, this is a classic traversal binary tree.

However, when you iterate, you should be careful not to iterate through the left subtree, then the right subtree, and then reverse the traversal result of the right subtree. This operation can pass 99% of the test cases, but still fail 1% of the test cases.

Why is that? Because the symmetric binary tree here is a mirror operation, no matter which order, order, order which traversal, reverse traversal results will not be mirrored, some special test cases are unable to pass, don’t ask why, I tried.

The rest of the way is only one node to a node of the contrast, if there is a child node, to reverse contrast child nodes, that for the first example, the first would be more about 2 nodes of the subtree, found the same, you should compare the left subtree 2 left child of the node tree node and right subtree 2 right subtree, so on, thus forming image comparison.

Not only do you get the right results, but you can also terminate the comparison early if you encounter different nodes, saving performance compared to getting all the nodes at once.

Let’s look at the code.

Your own answer

There is no

A better way (recursion)

Recursion is always easier than iteration, so let’s talk about recursion first. The whole idea is to start with the left and right nodes of the root node and do a mirror comparison 👇 :

function isSymmetric(root) {
  function check(p, q) {
    if(! p && ! q)return true
    if(! p || ! q)return false
    return p.val === q.val && check(p.left, q.right) && check(p.right, q.left)
  }
  return check(root.left, root.right)
}
Copy the code

The comparison process is divided into three main types:

  • pandqAre allnullTo prove that they are the same, returntrue
  • porqOne isnullTo prove that they are not the same, returnfalse
  • p.valandq.valReturns whether the values oftrueorfalse

After completing these three steps, we determine whether the values of the current two nodes are the same. Then we cross compare the left and right nodes of the two nodes, and we are done.

A Better Approach (iteration)

Iteration is similar to traversing a binary tree in that it requires a stack to store the current node.

At the beginning, the two nodes are pushed onto the stack, and then the iteration begins. The two nodes are taken out in turn, and the values of the two are compared. The comparison process is the same as recursion.

function isSymmetric(root) {
  function check(p, q) {
    const arr = [p, q]
    while (arr.length) {
      p = arr.shift()
      q = arr.shift()
      if(! p && ! q)continue
      if((! p || ! q) || (p.val ! == q.val))return false
      arr.push(q.left)
      arr.push(p.right)
      arr.push(q.right)
      arr.push(p.left)
    }
    return true
  }
  return check(root.left, root.right)
}
Copy the code




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)