最近一直在寫(xiě)Swift方面的算法問(wèn)題，寫(xiě)得多了，自然就有一定的收獲，今天有個(gè)問(wèn)題，感覺(jué)特別有趣??。

始

這個(gè)問(wèn)題是這樣的：確定一個(gè)二叉樹(shù)B是否是另外一個(gè)二叉樹(shù)A的子樹(shù)。
這個(gè)問(wèn)題不難，百度能找到很多的答案，其基本思路是這樣的，先遍歷first二叉樹(shù)，找到所有值等于second二叉樹(shù)根結(jié)點(diǎn)值的節(jié)點(diǎn)群。然后，再分別比較節(jié)點(diǎn)群里的節(jié)點(diǎn)的子樹(shù)節(jié)點(diǎn)和first節(jié)點(diǎn)的值是否相同，若能找到，就可以確定second二叉樹(shù)是first二叉樹(shù)的一個(gè)兒子??。

在C語(yǔ)言里，代碼是這樣寫(xiě)的：

struct BinaryTreeNode {
    int value;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};
//  判斷一個(gè)二叉樹(shù)是否是另一個(gè)的子樹(shù)
bool getAnswerWith(BinaryTreeNode * first,BinaryTreeNode * second){
    //遍歷first二叉樹(shù)，找到first節(jié)點(diǎn)與second根節(jié)點(diǎn)值相同的節(jié)點(diǎn)
    //??  這里完全可以使用遞歸的方式去遍歷A二叉樹(shù)，但是那樣不好，因?yàn)檫f歸深度過(guò)于深的話(huà)可能造成函數(shù)壓棧太多，造成棧溢出。
    //這里運(yùn)用壓棧的方式遍歷二叉樹(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)));
}

如果把這個(gè)代碼移植到Swift里，也很簡(jiǎn)單。照著翻譯一遍就好了。
翻譯好的代碼是這樣的：

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
    }
    /*同樣使用壓棧的方式遍歷二叉樹(shù)，這里的棧是我使用鏈表實(shí)現(xiàn)的，跟apple的文檔用Array的實(shí)現(xiàn)方式不太一樣
      有興趣的可以看下我的GitHub，下面會(huì)有我的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))
}

變

如果僅僅是這樣，也不會(huì)有什么特別的地方，最近一直在研究Swift的東西，所以想事情都會(huì)往Swift那邊靠一靠，
Swift里允許我們對(duì)運(yùn)算符進(jìn)行重載，而且需要注意的是，樹(shù)節(jié)點(diǎn)的value需要遵守Equatable協(xié)議才可以進(jìn)行比較，于是代碼就變成了這個(gè)樣子：

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里允許我們寫(xiě)運(yùn)算符的重載，很強(qiáng)大的特性，在很多地方，或者是復(fù)雜的函數(shù)嵌套時(shí)，我們都可以使用運(yùn)算符的重載，是代碼更簡(jiǎn)潔，加強(qiáng)可讀性。但是我把它用到這里，仔細(xì)想想，不大好，因?yàn)槲以贐inaryTreeNode里重載了==運(yùn)算符，意味著以后用到二叉樹(shù)的==都會(huì)是這樣子，使得我們的二叉樹(shù)有了很大的局限性，但是又想不到啥好的方法。為了更強(qiáng)的可讀、擴(kuò)展性和二叉樹(shù)的應(yīng)用范圍，我把代碼改成了這個(gè)樣子：

class BinaryTreeNode<T> {
    var value:T
    var left:BinaryTreeNode?
    var right:BinaryTreeNode?
    init(_ value:T) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}
//將兩個(gè)方法抽取出來(lái)
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!
    }
}

這樣寫(xiě)有上述的好處，但是還是不太好。因?yàn)橹灰鏄?shù)節(jié)點(diǎn)的值類(lèi)型遵守了Equatable協(xié)議，使用==的時(shí)候，就會(huì)使用我們定義的重載方法，還是給二叉樹(shù)增加了一定的局限性。

末

經(jīng)過(guò)一番的思考，我最后決定，把代碼改成最開(kāi)始時(shí)候的樣子??。有時(shí)候，語(yǔ)言特性的東西不一定適合我們的應(yīng)用場(chǎng)景，不要為了使用而去使用，否則得不償失。

上文說(shuō)到我最近在寫(xiě)一些Swift數(shù)據(jù)結(jié)構(gòu)和算法上面的東西，有需要的朋友可以看一下。
GitHub地址：https://github.com/chaiyanpu/SwiftCustomAlgorithms

-------------------2016年11月19號(hào)更新-------------------------

New Idea

感謝Swift3.0新增加的關(guān)鍵字fileprivate，現(xiàn)在只需要把 BinaryTreeNode<T> 定義 和 BinaryTreeNode拓展放到不同的文件中就可以了，修改后的代碼是這樣子的：

//注意，只需要前面加上fileprivate關(guān)鍵字，但是和BinaryTreeNode<T>不在一個(gè)文件中就可以了
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!
    }
}

感覺(jué)胸前的紅領(lǐng)巾更鮮艷了??。