未分類

Balanced Binary Tree

DepthFirstSearch, Go, LeetCode, Tree

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

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

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 isBalanced(root *TreeNode) bool {
}

解答思路:

這題單純的只是要判斷樹是否平衡而已，所幸不是要做複雜的樹平衡AVL，而既然要判斷是否平衡就需要知道左右子節點的最大深度，理所當然就先將判斷樹最大深度的部分寫出來，接著利用在判斷該節點的最大深度時必會先拿到左右子節點最大深度的特性，藉此將左右子節點最大深度做相減來判斷是否平衡，如果確定平衡才將該節點的最大深度向上回傳繼續做比較。

程式碼解說:

基本上與樹最大深度判斷所做的遞回後序遍歷非常相似，只是多了需要判斷平衡的部分，而在一開始如果節點為nil或已經到了樹的末端就回傳最大深度-1(因為該節點不存在)，既然是空節點就肯定沒有平衡問題就回傳true，而節點不為nil就繼續分成左右兩子節點做遞回，當左右子節點的值回來時，先判斷左右子樹是否已經平衡，接著才將左右子樹的最大深度相減是否超過1以此判斷該樹是否平衡，這邊要注意的是因為不曉得左右子樹誰的深度比較大，所以相減有負的情況也要考量進去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var maxRowL int
var maxRowR int
if node == nil {
	return maxRow - 1, true
}
maxRowL, balanceL := postOrderTravel(node.Left, maxRow+1)
maxRowR, balanceR := postOrderTravel(node.Right, maxRow+1)
if balanceL && balanceR {
	if maxRowL-maxRowR >= 0 && maxRowL-maxRowR <= 1 {
		return maxRowL, true
	} else if maxRowR-maxRowL >= 0 && maxRowR-maxRowL <= 1 {
		return maxRowR, true
	}
	return 0, false
}
return 0, false

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func isBalanced(root *TreeNode) bool {
	_, balance := postOrderTravel(root, 1)
	return balance
}
func postOrderTravel(node *TreeNode, maxRow int) (int, bool) {
	var maxRowL int
	var maxRowR int
	if node == nil {
		return maxRow - 1, true
	}
	maxRowL, balanceL := postOrderTravel(node.Left, maxRow+1)
	maxRowR, balanceR := postOrderTravel(node.Right, maxRow+1)
	if balanceL && balanceR {
		if maxRowL-maxRowR >= 0 && maxRowL-maxRowR <= 1 {
			return maxRowL, true
		} else if maxRowR-maxRowL >= 0 && maxRowR-maxRowL <= 1 {
			return maxRowR, true
		}
		return 0, false
	}
	return 0, false
}

總結:

判斷二元樹是否平衡時，不妨先將二元樹的最大深度給寫出來，利用計算最大深度會算出左右子樹的最大深度特性，將其稍作修改便能得知樹是否平衡。

分享到