未分類

Validate Binary Search Tree

DepthFirstSearch, Go, LeetCode, Tree

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

1
2
3
  2
 / \
1   3

Binary tree [2,1,3], return true.

Example 2:

1
2
3
  1
 / \
2   3

Binary tree [1,2,3], return false.

提示 解題應用
DepthFirstSearch InOrderTravel

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

解答思路:

要檢查一個二元樹是否有排序其實非常簡單，如果是一個二元搜尋樹的話，那麼只要中序遍歷其結果就會很神奇的由小排至大，所以利用這個特性只要一邊用中序遍歷一邊檢查此節點值是否比前一個大，直到全數遍歷完畢就可以確認是否為合法的二元搜尋樹。

程式碼解說:

因為要一邊用中序遍歷一邊檢查此節點值是否比前一個大，所以參數多一個變數用來儲存前一個節點的值以方便遍歷時能一邊比較，而因為比較的方式是檢查節點值是否比前一個大，所以一開始用0或是Int32位元的極小值做為初始值來讓根節點的值(第1個節點)能與暫存值比較，然而因為題目的測資都有設想到用這些值做為根節點的值，所以最後乾脆就直接用boolean值來判斷是否為初始值

1
2
3
4
5
func isValidBST(root *TreeNode) bool {
	var pre int
	init := true
	return inOrderTravel(root, &pre, &init)
}

接著就是開始處理中序遍歷的細節，如果節點為nil，表示樹的分支檢查到該處都沒有問題因此回傳true，而如果尚未遍歷完畢便繼續中序遍歷，待左子樹結果回傳，如果左子樹回傳出現false或非為根節點初始值的情況下，該節點的值比前一個節點值還小就直接回傳false，否則才繼續中序遍歷，並記得在那之前先將前一個節點值改為目前的節點值，當然後頭的節點遍歷就不再是根節點也一併將boolean值改為false，最後才遍歷右子樹的節點

1
2
3
4
5
6
7
8
9
10
11
12
func inOrderTravel(node *TreeNode, pre *int, init *bool) bool {
	if node == nil {
		return true
	}
	tmp := inOrderTravel(node.Left, pre, init)
	if !tmp || (!*init && node.Val <= *pre) {
		return false
	}
	*pre = node.Val
	*init = false
	return inOrderTravel(node.Right, pre, init)
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isValidBST(root *TreeNode) bool {
	var pre int
	init := true
	return inOrderTravel(root, &pre, &init)
}
func inOrderTravel(node *TreeNode, pre *int, init *bool) bool {
	if node == nil {
		return true
	}
	tmp := inOrderTravel(node.Left, pre, init)
	if !tmp || (!*init && node.Val <= *pre) {
		return false
	}
	*pre = node.Val
	*init = false
	return inOrderTravel(node.Right, pre, init)
}

總結:

要檢查一個二元搜尋樹是否確實排序的話，那麼只要中序遍歷其結果就會由小排至大，所以利用這個特性只要一邊用中序遍歷一邊檢查此節點值是否比前一個大，直到全數遍歷完畢就可以確認是否為合法的二元搜尋樹。

分享到