題目:檢查一棵二叉樹是否為二叉查找樹.
解法一
中序遍歷之后荷愕，如果數(shù)組是有序露戒，那么二叉樹是二叉查找樹.
<pre><code>` func copyBST(root:TreeNode?,data:inout [String]) {
if root == nil {
return
}
copyBST(root: root?.leftChild, data: &data)
data.append(root!.data!)
copyBST(root: root?.rightChild, data: &data)
}
func isBST(root:TreeNode?) -> Bool {
if root == nil {
return false
}
var data:[String] = []
copyBST(root: root, data: &data)
print("中序遍歷結(jié)果---\(data)")
for i in 0..<data.count - 1 {
if Int(data[i])! > Int(data[i + 1])! {
return false
}
}
return true
}`</code></pre>
解法二
中序遍歷的數(shù)組其實(shí)可以不用腿准，只需要記錄最后一次訪問的數(shù)字即可夭问，如果當(dāng)前數(shù)字小于最小數(shù)字則不成功.
<pre><code>` var lastNum:Int = Int.min
func isBST2(root:TreeNode?) -> Bool {
if root == nil {
return true
}
// 檢查左子樹
if !isBST2(root: root?.leftChild) {
return false
}
if Int(root!.data!)! <= lastNum {
return false
}
// 檢查右子樹
if !isBST2(root: root?.rightChild) {
return false
}
return true
}`</code></pre>
解法三
二叉查找樹的節(jié)點(diǎn)左邊所有的節(jié)點(diǎn)值都小于本身的數(shù)值倡蝙，右邊的數(shù)值都大于本身的數(shù)值予颤，如果數(shù)字在最大值和最小值中間則是成功.
<pre><code>` func isBST3(root:TreeNode?) -> Bool {
return checkBST3(node: root, min: Int.min, max: Int.max)
}
func checkBST3(node:TreeNode?,min:Int,max:Int) -> Bool {
if node == nil {
return true
}
let value:Int = Int(node!.data!)!
if value < min || value >= max {
return false
}
if !checkBST3(node: node?.leftChild, min: min, max: value) || !checkBST3(node: node?.rightChild, min: value, max: max){
return false
}
return true
}`</code></pre>
測(cè)試代碼:
<pre><code>`var isBST:Bool = binarySearchTree.isBST(root: searchNode)
if isBST {
print("FlyElephant---是二叉查找樹")
} else {
print("FlyElephant---不是二叉查找樹")
}
var isBST2:Bool = binarySearchTree.isBST2(root: searchNode)
if isBST2 {
print("FlyElephant---是二叉查找樹")
} else {
print("FlyElephant---不是二叉查找樹")
}
var isBST3:Bool = binarySearchTree.isBST3(root: searchNode)
if isBST3 {
print("FlyElephant---是二叉查找樹")
} else {
print("FlyElephant---不是二叉查找樹")
}`</code></pre>
