• 前序遍历： 144
• 后序遍历： 145
• 中序遍历： 94
• 层次遍历：102

public class TreeNode {
	public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
	public init(_ val: Int) {
		self.val = val
		self.left = nil
		self.right = nil
	}
}

这里帮助大家确定下来递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

class Solution {
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        traversal(root, &result)
        return result
    }

    private func traversal(_ cur: TreeNode?, _ result: inout [Int]) {
        guard let cur = cur else { return }
        result.append(cur.val)
        traversal(cur.left, &result)
        traversal(cur.right, &result)
    }
}

class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        traversal(root, &result)
        return result
    }
    func traversal(_ root: TreeNode?, _ result: inout [Int]) {
        guard let cur = root else { return }
        traversal(cur.left, &result)
        result.append(cur.val)
        traversal(cur.right, &result)
    }
}

class Solution {
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        traversal(root, &result)
        return result
    }

    private func traversal(_ cur: TreeNode?, _ result: inout [Int]) {
        guard let element = cur else { return }
        traversal(element.left, &result)
        traversal(element.right, &result)
        result.append(element.val)
    }
}

• 方法1：

    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let element = root else { return [] }
        var result = [Int]()
        var stack = [element]
        while !stack.isEmpty {
            let node = stack.removeLast()
            result.append(node.val)
            if let right = node.right {
                stack.append(right)
            }
            if let left = node.left {
                stack.append(left)
            }
        }
        return result
    }

• 方法2：

    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let element = root else { return [] }

        var result = [Int]()
        var stack = [TreeNode]()
        
        // 初始化时指向element
        var cur = root
        
        // 循环条件：要么cur不空，要么stack不空
        while cur != nil || !stack.isEmpty {
            while cur != nil {
                stack.append(cur!)
                result.append(cur!.val)
                cur = cur!.left
            }
            let node = stack.removeLast()
            cur = node.right
        }
        return result
    }

//中序非递归
//思路：通过stack 保存已经访问的元素，用于原路返回
func inorderTraversal(_ root: TreeNode?) ->[Int] {
    guard root != nil  else { return [] }
    var result = [Int]()
    var stack = [TreeNode]()
    var cur = root
    while cur != nil || stack.count != 0 {
        while cur != nil {
            stack.append(cur!)
            cur = cur!.left
        }
        let node = stack.removeLast()
        result.append(node.val)
        cur = node.right
    }
    return result
}

• 方法1

    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let element = root else { return [] }
        var result = [Int]()
        var stack = [element]
        // 按中右左的顺序访问，然后逆序输出即为后序遍历
        while !stack.isEmpty {
            let topNode = stack.removeLast()
            result.append(topNode.val)
            if topNode.left != nil {
                stack.append(topNode.left!)
            }
            if topNode.right != nil {
                stack.append(topNode.right!)
            }
        }
        //反转
        result.reverse()
        return result
    }

• 方法2

    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        guard root != nil else { return []  }
        var result = [Int]()
        var stack = [TreeNode]()
        //lastVisit标识上次（刚刚访问的结点）
        var lastVisit: TreeNode?    
        var cur = root
        while cur != nil || !stack.isEmpty {
            while cur != nil {
                stack.append(cur!)
                cur = cur!.left
            }
            //现在cur指向nil
            //现在栈顶是最左结点，无需访问更左，如果没有右孩子或者右孩子刚访问过，则访问自身
            let top = stack.last!//这里先看看，先不弹出
            
            if top.right == nil || top.right === lastVisit {//注意是===全等，==用于判断值相等并且需要遵循Equatable协议
                let node = stack.removeLast()
                result.append(node.val)
                lastVisit = node
            }else{
                cur = top.right
            }
        }
        return result
    }