最近一直在寫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!
    }
}

感覺胸前的紅領巾更鮮艷了??。