未分類

Same Tree

DepthFirstSearch, Go, LeetCode, Tree

Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

提示 解題應用
Tree 樹的遍歷方式
DepthFirstSearch 前序遍歷

Default:

1
2
3
func preOrderTravel(p *TreeNode, q *TreeNode) bool {
}

解答思路:

既然要比較兩個樹是否相同的話，就意味著需要做樹的遍歷，而二元樹的遍歷一般來說就想到前序、中序與後續遍歷，因為我們需要先比較值是否相同才繼續往下，所以就採用前序遍歷的方式來處理，既然用上了遞回來處理自然程式的編寫上就輕鬆不少。

程式碼解說:

為了加快判斷兩二元樹是否完全相同，首先可以先確認樹的形狀是否相同，可以先藉由兩兩節點是否都同時存在來決定，這在遍歷到樹的末支節點時可以少幾個步驟，不必每次都去取得節點的值才做判斷，而一定要到最後兩兩皆不存在，也就是到末支節點了才可以回傳true，若先前的形狀都相同的話，再來才是判斷兩兩節點的值是否相同，如果也沒有問題的話，這時才將二元樹分拆成左二元樹與右二元樹再重新遞回，如果有其中一個分支回傳false就會依序往上遞回回去，表示並非完全相同，直到所有二元樹的節點完全遍歷後沒有問題，最終才能夠確信這是兩棵完全相同的二元樹。

1
2
3
4
5
6
if p == nil && q == nil {
	return true
} else if p == nil || q == nil {
	return false
}
return (p.Val == q.Val) && preOrderTravel(p.Left, q.Left) && preOrderTravel(p.Right, q.Right)

完整程式碼:

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

總結:

若需要比對兩二元樹是否完全相同，可以用前序遍歷的方式來做，先行判斷再來決定要不要再繼續進行樹的遍歷，除了值是否相同之外，也可以透過兩兩節點是否都存在斷定樹的形狀，來提前得知是否兩二元樹完全相同。

分享到