【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Leecode 101. Symmetric binary trees

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

 

For example, binary trees [1,2,2,3,4,4,3] are symmetric.

 

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

 

Advanced:

Can you solve this problem both recursively and iteratively?

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

GO language version of recursion

  1. You know, this is a tree, it’s just represented as an array

Let’s take this tree as an example

Because of the need for symmetry, we put in two identical trees P, Q, if the root of the same tree P, Q is the same, the left node of the p tree is not empty and the right node of Q is not empty &&q the left node of the q tree is not empty and the right node of P is not empty

Or both the left and right nodes are empty. As long as one is empty and the other is not empty, it is definitely not a symmetric binary tree.

func isSymmetric(root *TreeNode) bool {
    return check(root, root)
}

func check(p, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left) 
}

Copy the code

The iterative version

  1. Define a queue (fifo)

  2. Add the tree to the queue twice

  3. The queue length is greater than 0

  4. I’m pulling out the two trees in the queue, u, V

  5. If both are empty, continue

  6. If one is null and one is not null, it is not a symmetric binary tree.

  7. This tree has a different root, and it’s not a binary tree.

  8. Add the left node of the tree u to the queue

  9. Add the right node of the tree v to the queue. (Because the queue is first in, first out, they are also first out.)

  10. Add the right node of the tree u to the queue

  11. Add the left node of the tree v to the queue

func isSymmetric(root *TreeNode) bool {
    u, v := root, root        / / 1.
    q := []*TreeNode{}
    q = append(q, u)   
    q = append(q, v)         / / 2.
    for len(q) > 0 {         / / 3.
        u, v = q[0], q[1]
        q = q[2:]            / / 4.
        if u == nil && v == nil {  / / 5.
            continue
        }
        if u == nil || v == nil {  / / 6.
            return false
        }
        ifu.Val ! = v.Val {/ / 7.
            return false
        }
        q = append(q, u.Left)     / / 8.
        q = append(q, v.Right)    / / 9.

        q = append(q, u.Right)    / / 10.
        q = append(q, v.Left)     / / 11.
    }
    return true
}

Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️