【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.
😄
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
- 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
-
Define a queue (fifo)
-
Add the tree to the queue twice
-
The queue length is greater than 0
-
I’m pulling out the two trees in the queue, u, V
-
If both are empty, continue
-
If one is null and one is not null, it is not a symmetric binary tree.
-
This tree has a different root, and it’s not a binary tree.
-
Add the left node of the tree u to the queue
-
Add the right node of the tree v to the queue. (Because the queue is first in, first out, they are also first out.)
-
Add the right node of the tree u to the queue
-
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! ❤ ️ ❤ ️ ❤ ️ ❤ ️