二叉樹(shù)的三種遍歷
二叉樹(shù)
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)
}
}
另外
不得不說(shuō)淀零，得到二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果或者后序遍歷和中序遍歷的結(jié)果，是可以還原二叉樹(shù)膛壹。
二叉搜索樹(shù)的特性是中序遍歷得到的結(jié)果是有序的驾中，此特性極為重要，也因?yàn)榇颂匦阅Ａ嫠阉鳂?shù)只需要前序遍歷的結(jié)果或者后序遍歷的結(jié)果即可還原二叉樹(shù)肩民。原因是前序后序的結(jié)果排序后即可得到中序遍歷的結(jié)果。
