相對(duì)來(lái)說(shuō)缩擂，這三種代碼相似度較高，而且是真正按順序遍歷胯盯，沒(méi)有反轉(zhuǎn)等操作博脑。

前序遍歷

前序遍歷相對(duì)簡(jiǎn)單，先訪問(wèn)該節(jié)點(diǎn)叉趣，然后訪問(wèn)左右節(jié)點(diǎn)疗杉，利用棧的性質(zhì)反向壓入右左節(jié)點(diǎn)即可蚕礼。

中序后序遍歷

中序和后序遍歷的主要思想就是先找到最左邊的葉子結(jié)點(diǎn)梢什，然后出棧的時(shí)候需不需要將該節(jié)點(diǎn)的右子樹(shù)納入考察范圍，也就是說(shuō)該右子樹(shù)有沒(méi)有被考察過(guò)（空自然不需要考察）嗡午，中序遍歷無(wú)需此判斷，后序遍歷需要荔睹，僅此而已。后序遍歷就多了一個(gè)pre指針記錄上一個(gè)訪問(wèn)的節(jié)點(diǎn)宵距，也完全可以用 isVisted 屬性來(lái)替代中姜。

    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        let stack = ArrayStack<TreeNode>()
        var result = Array<Int>()
        
        stack.push(element: root)
        while stack.isEmpty() == false {
            let nowNode = stack.pop()
            result.append(nowNode.val)
            if let right = nowNode.right {
                stack.push(element: right)
            }
            if let left = nowNode.left {
                stack.push(element: left)
            }
        }
        return result
    }
    
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var root = root
        let stack = ArrayStack<TreeNode>()
        var result = Array<Int>()
        
        while root != nil || stack.isEmpty() == false {
            if root != nil {
///向左走到底
                stack.push(element: root!)
                root = root?.left
            } else {
///訪問(wèn)該節(jié)點(diǎn)同時(shí)將考察節(jié)點(diǎn)替換為該節(jié)點(diǎn)右子樹(shù)丢胚，葉子結(jié)點(diǎn)右子樹(shù)為空，繼續(xù) pop兔跌，非葉子節(jié)點(diǎn)右子樹(shù)不為空峡蟋，被壓入棧從而實(shí)現(xiàn)左中右遍歷順序
                let now = stack.pop()
                result.append(now.val)
                root = now.right
            }
        }
        
        return result
    }
    
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var root = root
        let stack = ArrayStack<TreeNode>()
        var result = Array<Int>()
        var pre: TreeNode? = nil
        
        while root != nil || stack.isEmpty() == false {
            if root != nil {
                stack.push(element: root!)
                root = root?.left
            } else {
                let now = stack.top()
///唯一不同，不是直接出棧仅乓，而要先判斷該節(jié)點(diǎn)的右子樹(shù)是否應(yīng)該考察
                if now.right == nil || now.right === pre {
///不需要考察變走中序遍歷邏輯蓬戚，順便記錄下現(xiàn)在訪問(wèn)的節(jié)點(diǎn)。此時(shí) root 一定為空豫喧，在棧的結(jié)構(gòu)中幢泼，下一個(gè)待訪問(wèn)節(jié)點(diǎn)便是當(dāng)前節(jié)點(diǎn)的父親節(jié)點(diǎn)
                    stack.pop()
                    result.append(now.val)
                    pre = now
                } else {
///應(yīng)該考察就直接賦值，重回循環(huán)
                    root = now.right
                }
            }
        }
        
        return result
    }

///自定義的數(shù)據(jù)結(jié)構(gòu)
protocol Stack {
    associatedtype ItemType
    
    func getSize() -> Int
    func isEmpty() -> Bool
    func push(element: ItemType)
    func pop() -> ItemType
    func top() -> ItemType
}

class ArrayStack<T>: CustomStringConvertible, Stack {
    private var array: Array<T>
    
    var description: String {
        var des = "["
        for i in 0 ..< array.count {
            des += "\(array[i])"
            if i != (array.count - 1) {
                des += ", "
            }
        }
        des += "] top"
        return des
    }
    
    init(capacity: Int) {
        array = Array.init()
        array.reserveCapacity(capacity)
    }
    
    convenience init() {
        self.init(capacity: 10)
    }
    
    //MARK: - Stack
    func getSize() -> Int {
        return array.count
    }
    
    func isEmpty() -> Bool {
        return array.isEmpty
    }
    
    func push(element: T) {
        array.append(element)
    }
    
    @discardableResult func pop() -> T {
        return array.removeLast()
    }
    
    func top() -> T {
        return array.last!
    }
}

附帶流程圖

前序

IMG_1747.jpg

中序

IMG_1748.jpg

后序

IMG_1749.jpg