最近一直在寫Swift方面的算法問題，寫得多了颓鲜，自然就有一定的收獲表窘，今天有個問題，感覺特別有趣??甜滨。
始
這個問題是這樣的：確定一個二叉樹B是否是另外一個二叉樹A的子樹乐严。
這個問題不難，百度能找到很多的答案衣摩，其基本思路是這樣的麦备，先遍歷first二叉樹，找到所有值等于second二叉樹根結點值的節(jié)點群昭娩。然后凛篙，再分別比較節(jié)點群里的節(jié)點的子樹節(jié)點和first節(jié)點的值是否相同，若能找到栏渺，就可以確定second二叉樹是first二叉樹的一個兒子??呛梆。
在C語言里，代碼是這樣寫的：
struct BinaryTreeNode {
int value;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
// 判斷一個二叉樹是否是另一個的子樹
bool getAnswerWith(BinaryTreeNode * first,BinaryTreeNode * second){
//遍歷first二叉樹磕诊，找到first節(jié)點與second根節(jié)點值相同的節(jié)點
//?? 這里完全可以使用遞歸的方式去遍歷A二叉樹填物，但是那樣不好纹腌，因為遞歸深度過于深的話可能造成函數(shù)壓棧太多，造成棧溢出滞磺。
//這里運用壓棧的方式遍歷二叉樹
std::stack<BinaryTreeNode *> myStack;
BinaryTreeNode * tree = first;
bool answer = false;
while (myStack.size() != 0 || tree != NULL) {
if (tree != NULL){
myStack.push(tree);
if (tree->value == second->value){
answer = isHasCommonValue(tree, second);
}
tree = tree->left;
}else{
tree = myStack.top()->right;
myStack.pop();
}
}
return answer;
}
bool isHasCommonValue(BinaryTreeNode * first,BinaryTreeNode *second){
if (second == NULL){ return true;}
if (second->value != first->value){ return false;}
return (isHasCommonValue(first->left, second->left) && (isHasCommonValue(first->right, second->right)));
}
如果把這個代碼移植到Swift里升薯，也很簡單。照著翻譯一遍就好了击困。
翻譯好的代碼是這樣的：
class BinaryTreeNode<T> {
var value:T
var left:BinaryTreeNode?
var right:BinaryTreeNode?
init(_ value:T) {
self.value = value
self.left = nil
self.right = nil
}
}
func getAnswerWithSwift(_ first:BinaryTreeNode<Int>,second:BinaryTreeNode<Int>?) -> Bool{
if second == nil {
return true
}
/*同樣使用壓棧的方式遍歷二叉樹涎劈，這里的棧是我使用鏈表實現(xiàn)的，跟apple的文檔用Array的實現(xiàn)方式不太一樣
有興趣的可以看下我的GitHub阅茶，下面會有我的GitHub地址
*/
let stack:Stack<BinaryTreeNode<Int>> = Stack()
var answer:Bool = false
var tree:BinaryTreeNode<Int>? = first
while !stack.isEmpty() || tree != nil {
if let aTree = tree {
stack.push(value: aTree)
if aTree.value == second!.value{
answer = isHasCommonValue(aTree,second)
}
tree = aTree.left
}else{
tree = stack.top()?.right
stack.pop()
}
}
return answer
}
func isHasCommonValue(_ first:BinaryTreeNode<Int>?,_ second:BinaryTreeNode<Int>?) -> Bool{
if second == nil{ return true}
if first == nil { return false}
if first!.value != second!.value{return false}
return (isHasCommonValue(first!.left,second!.left) && isHasCommonValue(first!.right,second!.right))
}
變
如果僅僅是這樣蛛枚，也不會有什么特別的地方，最近一直在研究Swift的東西脸哀，所以想事情都會往Swift那邊靠一靠蹦浦，
Swift里允許我們對運算符進行重載，而且需要注意的是撞蜂，樹節(jié)點的value需要遵守Equatable協(xié)議才可以進行比較盲镶，于是代碼就變成了這個樣子：
class BinaryTreeNode<T:Equatable>:Equatable {
var value:T
var left:BinaryTreeNode?
var right:BinaryTreeNode?
init(_ value:T) {
self.value = value
self.left = nil
self.right = nil
}
//重載 ==
static func ==(lhs: BinaryTreeNode<T>, rhs: BinaryTreeNode<T>) -> Bool{
if lhs.value != rhs.value{
return false
}
return (isNil(lhs:lhs.left,rhs:rhs.left) && isNil(lhs:lhs.right,rhs:rhs.right))
}
static func isNil(lhs:BinaryTreeNode<T>?,rhs:BinaryTreeNode<T>?) -> Bool{
if rhs == nil { return true}
if lhs == nil {return false}
return rhs! == lhs!
}
}
func getAnswerWithSwift(_ first:BinaryTreeNode<Int>,second:BinaryTreeNode<Int>?) -> Bool{
if second == nil {
return true
}
let stack:Stack<BinaryTreeNode<Int>> = Stack()
var answer:Bool = false
var tree:BinaryTreeNode<Int>? = first
while !stack.isEmpty() || tree != nil {
if let aTree = tree {
stack.push(value: aTree)
if aTree.value == second!.value{
answer = (aTree == second!) //注意這里
}
tree = aTree.left
}else{
tree = stack.top()?.right
stack.pop()
}
}
return answer
}
Swift里允許我們寫運算符的重載，很強大的特性蝌诡，在很多地方徒河，或者是復雜的函數(shù)嵌套時，我們都可以使用運算符的重載送漠，是代碼更簡潔顽照，加強可讀性。但是我把它用到這里闽寡，仔細想想代兵，不大好，因為我在BinaryTreeNode里重載了==運算符爷狈，意味著以后用到二叉樹的==都會是這樣子植影，使得我們的二叉樹有了很大的局限性，但是又想不到啥好的方法涎永。為了更強的可讀思币、擴展性和二叉樹的應用范圍，我把代碼改成了這個樣子：
class BinaryTreeNode<T> {
var value:T
var left:BinaryTreeNode?
var right:BinaryTreeNode?
init(_ value:T) {
self.value = value
self.left = nil
self.right = nil
}
}
//將兩個方法抽取出來
extension BinaryTreeNode where T:Equatable {
static func ==(lhs: BinaryTreeNode<T>, rhs: BinaryTreeNode<T>) -> Bool{
if lhs.value != rhs.value{
return false
}
return (isNil(lhs:lhs.left,rhs:rhs.left) && isNil(lhs:lhs.right,rhs:rhs.right))
}
static func isNil(lhs:BinaryTreeNode<T>?,rhs:BinaryTreeNode<T>?) -> Bool{
if rhs == nil {
return true
}
if lhs == nil {
return false
}
return rhs! == lhs!
}
}
這樣寫有上述的好處羡微，但是還是不太好谷饿。因為只要二叉樹節(jié)點的值類型遵守了Equatable協(xié)議，使用==的時候妈倔，就會使用我們定義的重載方法博投，還是給二叉樹增加了一定的局限性。
末
經(jīng)過一番的思考盯蝴，我最后決定毅哗，把代碼改成最開始時候的樣子??听怕。有時候，語言特性的東西不一定適合我們的應用場景虑绵，不要為了使用而去使用尿瞭，否則得不償失。
上文說到我最近在寫一些Swift數(shù)據(jù)結構和算法上面的東西翅睛，有需要的朋友可以看一下声搁。
GitHub地址：https://github.com/chaiyanpu/SwiftCustomAlgorithms
-------------------2016年11月19號更新-------------------------
New Idea
感謝Swift3.0新增加的關鍵字fileprivate，現(xiàn)在只需要把 BinaryTreeNode<T> 定義 和 BinaryTreeNode拓展放到不同的文件中就可以了宏所，修改后的代碼是這樣子的：
//注意酥艳，只需要前面加上fileprivate關鍵字摊溶，但是和BinaryTreeNode<T>不在一個文件中就可以了
fileprivate extension BinaryTreeNode where T:Equatable {
static func ==(lhs: BinaryTreeNode<T>, rhs: BinaryTreeNode<T>) -> Bool{
if lhs.value != rhs.value{
return false
}
return (isNil(lhs:lhs.left,rhs:rhs.left) && isNil(lhs:lhs.right,rhs:rhs.right))
}
static func isNil(lhs:BinaryTreeNode<T>?,rhs:BinaryTreeNode<T>?) -> Bool{
if rhs == nil {
return true
}
if lhs == nil {
return false
}
return rhs! == lhs!
}
}
感覺胸前的紅領巾更鮮艷了??爬骤。
