采用Swift 5

递归的本质就是采用的内存栈
非递归方式，就采用栈的方式（后序的非递归较为复杂，需要记录上次输出节点与当前遍历到的节点进行判断，如果是左子树回退，去遍历当前的节点的右子树，如果是右子树回退栈就直接输出节点）

节点定义

class TreeNode: Equatable {var left: TreeNode?var right: TreeNode?var data: Int?init(left: TreeNode?, right: TreeNode?, data: Int?) {self.left = leftself.right = rightself.data = data}/// 正常这边应该是判断对应的指针地址是否相同（这边简单做处理）static func == (lhs: TreeNode, rhs: TreeNode) -> Bool {return  (lhs.left == rhs.left)  && (lhs.right == rhs.right) && (lhs.data == rhs.data)}
}

非递归的遍历

• 先序遍历

/// 非递归方式
func preOrderTraveralWithStack(node: TreeNode) {var stack: [TreeNode?] = []var root: TreeNode? = nodewhile root != nil || !stack.isEmpty {while root != nil {print(root?.data)stack.append(root)root = root?.left}if root == nil && !stack.isEmpty {root = stack.last!?.rightstack.removeLast()}}
}/// 递归方式
func preOrderTraveral(node: TreeNode?) {if node == nil {return}print(node?.data)preOrderTraveral(node: node?.left)preOrderTraveral(node: node?.right)
}

• 中序遍历

 /// 非递归方式
func midOrderTraveralWithStack(node: TreeNode) {var stack: [TreeNode?] = []var root: TreeNode? = nodewhile root != nil || !stack.isEmpty {while root != nil {stack.append(root)root = root?.left}if !stack.isEmpty {print(stack.last??.data)root = stack.last!?.rightstack.removeLast()}}
}/// 递归方式
func preOrderTraveral(node: TreeNode?) {if node == nil {return}preOrderTraveral(node: node?.left)print(node?.data)preOrderTraveral(node: node?.right)
}

• 后序遍历

 /// 非递归方式
func lastOrderTraveralWithStack(node: TreeNode) {var stack: [TreeNode?] = []var root: TreeNode? = node/// 用于记录上次输出的节点(如果是左子树回退需要遍历对应的右子树，如果是右子树回去直接输出)var flagNode: TreeNode?while root != nil || !stack.isEmpty {while root != nil {stack.append(root)root = root?.left}root = stack.last as? TreeNodeflagNode = nilwhile !stack.isEmpty {if root?.right == flagNode {print(root?.data)flagNode = rootstack.removeLast()root = stack.last as? TreeNode} else {root = root?.rightbreak}}}
}/// 递归方式
func preOrderTraveral(node: TreeNode?) {if node == nil {return}preOrderTraveral(node: node?.left)preOrderTraveral(node: node?.right)print(node?.data)
}