二叉树的三种遍历
二叉树
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 {
var array = [Int]()
func preorderTraversal(_ root: TreeNode?) -> [Int] {
guard let _root = root else { return array }
myPreorderTraversal(_root)
return array
}
func myPreorderTraversal(_ root: TreeNode?) {
guard let _root = root else { return }
array.append(_root.val)
myPreorderTraversal(_root.left)
myPreorderTraversal(_root.right)
}
}
中序遍历
class Solution {
var array = [Int]()
func inorderTraversal(_ root: TreeNode?) -> [Int] {
guard let _root = root else { return array }
myInorderTraversal(_root)
return array
}
func myInorderTraversal(_ root: TreeNode?) {
guard let _root = root else { return }
myInorderTraversal(_root.left)
array.append(_root.val)
myInorderTraversal(_root.right)
}
}
后序遍历
class Solution {
var array = [Int]()
func postorderTraversal(_ root: TreeNode?) -> [Int] {
guard let _root = root else { return array }
myPostorderTraversal(_root)
return array
}
func myPostorderTraversal(_ root: TreeNode?) {
guard let _root = root else { return }
myPostorderTraversal(_root.left)
myPostorderTraversal(_root.right)
array.append(_root.val)
}
}
另外
不得不说，得到二叉树的前序遍历和中序遍历的结果或者后序遍历和中序遍历的结果，是可以还原二叉树。
二叉搜索树的特性是中序遍历得到的结果是有序的，此特性极为重要，也因为此特性，二叉搜索树只需要前序遍历的结果或者后序遍历的结果即可还原二叉树。原因是前序后序的结果排序后即可得到中序遍历的结果。
