未分類

Symmetric Tree

BreadthFirstSearch, DepthFirstSearch, Go, LeetCode, Tree

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

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

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

Note:

Bonus points if you could solve it both recursively and iteratively.

提示 解題應用
Tree 樹的遍歷方式
BreadthFirstSearch Quene

Default:

1
2
3
4
5
6
7
8
9
10
11
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
}

解答思路:

這題需要判斷是不是一棵對稱樹，想必馬上就知道要樹的每一橫排來分別比對，進一步了解到要用廣度優先遍歷的方式來做，而對稱樹不一定是完全二元樹，所以意味著下述情況也是對稱:

1
2
3
4
5
  1
 / \
2   2
 \ / 
 3 3

這表示要考慮到不存在節點的位置是否也對稱，而在最初的想法中我利用做假點的方式，也就是遇上值為nil的情況就自己加了一個值為int32位元的最小值，可是這會碰到一個問題，在最後樹末點時值也是nil，就算你寫若其節點為nil值就不再新增左、右兩個假節點，這樣頂多就是再檢查一排nil的值，但是如果又碰上了極端的情況:

1
2
3
4
5
6
7
      1
     / \
    2   2
   /     \
  3       3
 /         \
4           4

這會使得自己陷入了兩難，所以可見得做假點的方式行不通，那麼要有其它的方式來判斷對稱，就是將整個樹再複製一份，一棵樹一律先往左邊跑，另一棵則是一律先往右邊，如此一來只要知道這左右兩邊節點的值是否相同就可以很輕易的知道是否對稱，當p節點往左就看q節點往右的值，而p節點換往右就看q節點往左的值，這也少了很多如果是做假點的話會碰上的麻煩，像是還需要二個陣列以中央為準，其一為左側廣度遍歷依序放入，而過了中央後廣度遍歷放入另一則要反著放，最後還要再判斷兩陣列是否相同簡直耗費太多時間，而用stack來存每列也行不通，stack為判斷一對一的對應關係而非對稱，就像是括號相對的關係 {()[]{}[()]} 這也不是對稱，同理此題也是如此，最後如果沒有上述錯誤的思考方向，那麼接下來的只要再用隊列來做廣度優先遍歷就可以解決了。

程式碼解說:

這邊我是用LinkedList的方式來實現隊列，當然也可以用陣列的方式來實現，作法因人而異

1
2
3
4
type QueneNode struct {
    Node *TreeNode
    Next *QueneNode
}

如果根節點為nil就直接丟回true，若有存在就繼續往下走，這邊我們因為要複製為兩棵樹，說穿了就是同時遍歷這棵樹兩次罷了，所以我們就連續將兩個根節點放入隊列之中，然後用front標定隊列的起始點以利判定隊列是否還有節點，而rear則是隊列的尾巴方便找到下一次插入點，這邊只用上一個隊列來儲存，當然也可以一樣用兩個隊列來分別取出比較，只是如果是一個隊列的話，在儲存方面每次就要分別塞兩個節點，同樣的在比較的時候就要一次取出兩個節點

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if root == nil {
    return true
}
var tmp *QueneNode
var front *QueneNode
var rear *QueneNode
tmp = &QueneNode{}
tmp.Node = root
front = tmp
rear = tmp
tmp = &QueneNode{}
tmp.Node = root
rear.Next = tmp
rear = tmp

p與q就是每次從隊列中取出兩個點來比較，如果節點都是nil表示左右對稱就繼續檢查下一組，記得要繼續之前要先把front移到下一組節點的開頭，否則會因為兩節點值不變而進入死回圈。接著只要其中一組為nil另一組不是，就意味著不對稱便直接回傳false，最後檢查這兩個節點的值是否相同，然後才接著依續去塞入其子節點，這邊要注意的是在塞入時的順序，因為每次都是取出p、q兩點來檢查是否相同，那我們為了要知道是否對稱，所以在子節點要放入隊列時就要以p的左子節點與q的右子節點為一組，再來是p的右子節點與q的左子節點為一組，如此一來在從隊列取出的時候就只要檢查其值兩兩是否相同就好，不用在考慮現在的節點是左邊還右邊或者對不對稱的問題

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
36
var p *QueneNode
var q *QueneNode
for front != nil {
	p = front
	q = front.Next
	if p.Node == nil && q.Node == nil {
		front = front.Next.Next
		continue
	} else if p.Node == nil || q.Node == nil {
		return false
	} else if p.Node.Val != q.Node.Val {
		return false
	}
	tmp = &QueneNode{}
	tmp.Node = p.Node.Left
	rear.Next = tmp
	rear = tmp
	
	tmp = &QueneNode{}
	tmp.Node = q.Node.Right
	rear.Next = tmp
	rear = tmp
	
	tmp = &QueneNode{}
	tmp.Node = p.Node.Right
	rear.Next = tmp
	rear = tmp
	
	tmp = &QueneNode{}
	tmp.Node = q.Node.Left
	rear.Next = tmp
	rear = tmp
	
	front = front.Next.Next
}
return true

完整程式碼:

Iteratively:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
type QueneNode struct {
	Node *TreeNode
	Next *QueneNode
}
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	var tmp *QueneNode
	var p *QueneNode
	var q *QueneNode
	var front *QueneNode
	var rear *QueneNode
	tmp = &QueneNode{}
	tmp.Node = root
	front = tmp
	rear = tmp
	tmp = &QueneNode{}
	tmp.Node = root
	rear.Next = tmp
	rear = tmp
	for front != nil {
		p = front
		q = front.Next
		if p.Node == nil && q.Node == nil {
			front = front.Next.Next
			continue
		} else if p.Node == nil || q.Node == nil {
			return false
		} else if p.Node.Val != q.Node.Val {
			return false
		}
		tmp = &QueneNode{}
		tmp.Node = p.Node.Left
		rear.Next = tmp
		rear = tmp
		tmp = &QueneNode{}
		tmp.Node = q.Node.Right
		rear.Next = tmp
		rear = tmp
		tmp = &QueneNode{}
		tmp.Node = p.Node.Right
		rear.Next = tmp
		rear = tmp
		tmp = &QueneNode{}
		tmp.Node = q.Node.Left
		rear.Next = tmp
		rear = tmp
		front = front.Next.Next
	}
	return true
}

Recursively:

1
2
3
4
5
6
7
8
9
10
11
12
13
func isSymmetric(root *TreeNode) bool {
	return preOrderTravel(root, root)
}
func preOrderTravel(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	} else if p == nil || q == nil {
		return false
	} else if p.Val != q.Val {
		return false
	}
	return true && preOrderTravel(p.Left, q.Right) && preOrderTravel(p.Right, q.Left)
}

總結:

二元樹的對稱不一定是完全二元樹，所以要考慮空節點的位置，其中做假節點的方式行不通尤其碰上了極端的樹狀會陷入兩難，此外也不能用stack來檢查每列是否對稱，stack僅能判定一對一的關係而非對稱，所以比較好的方式是在完全複製一棵樹，其一p樹的左子節點與另一q樹的右子節點為一組，再來則是p樹的右子節點與q樹的左子節點為一組，兩組分別進入隊列來同時做廣度優先遍歷，如此一來只要每次都從隊列取兩點來檢查值是否相同就好，不需要擔心是否對稱的問題。

分享到