二叉树的遍历
- 前序：根节点->左子树->右子树
- 中序：左子树->根节点->右子树
- 后序：左子树->右子树->根节点
- 层序：每一层从左到右输出
备注：前中后是以根节点的位置来说的。
实例
- 根据前序、中序遍历，输出后序遍历
class BackOrder {
var res: [Int] = []
var pre: [Int] = []
var inorder: [Int] = []
/// 根据前序、中序遍历输出二叉树的后序遍历
func buildBackOrder(pre: [Int], inorder: [Int]) -> [Int] {
self.pre = pre
self.inorder = inorder
getNode(root: 0, start: 0, end: inorder.count - 1)
return res
}
/// - Parameter root: 前序遍历根结点位置
/// - Parameter start: 中序遍历子树起始位置
/// - Parameter end: 中序遍历子树结束位置
func getNode(root: Int, start: Int, end: Int) {
guard start <= end else { return }
var left = start
// 定位跟在中序遍历中的位置
while left <= end && inorder[left] != pre[root] {
left += 1
}
// 递归处理左子树
getNode(root: root + 1, start: start, end: left - 1)
// 递归处理右子树
// 需要找到前序遍历中右子树的起始位置，left - right 表示左子树的数量， + 1 为根结点
getNode(root: root + left - start + 1, start: left + 1, end: end)
res.append(pre[root])
}
}
