Contents

# 101. Symmetric Tree

## 題目 :

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 } ``````