101. Symmetric Tree
Level : Easy
題目 :
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example :
Note
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
解題思路 :
- 這題需要我們辨認這個binary tree是否對稱
- 所以起始點並不在root，而是在 left = root.Left , right = root.Right作為起點
- 第一個level會比較 (left.Left , right.Right) 與 (left.Right, right.Left)
- 所以就可以掌握這個基本的邏輯，然後以同個邏輯往下做
Recursive的解法
- time complexity: O(n) , space complexity: O(1)
Runtime: 0 ms, faster than 100.00% of Go online submissions for Symmetric Tree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
return Visit(root.Left, root.Right)
}
func Visit(left *TreeNode, right *TreeNode) bool {
if left == nil && right == nil {
return true
}
if left == nil || right == nil {
return false
}
if left.Val != right.Val {
return false
}
return Visit(left.Left, right.Right) && Visit(left.Right, right.Left)
}
|
Iterative的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
queue := []*TreeNode{
root.Left,
root.Right,
}
for len(queue) != 0 {
left := queue[0]
right := queue[1]
queue = queue[2:]
if left == nil && right == nil {
continue
}
if left == nil || right == nil || left.Val != right.Val {
return false
}
queue = append(queue, left.Left, right.Right, left.Right, right.Left)
}
return true
}
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life”
我們峰頂見!!!
StevenLin's Blog