二元樹的走訪(前序、中序、後序)

使用Swift

/*
 * 給出一個整數陣列。
 * 按順序遍歷二元樹（Pre_Order、In_Order、Post_Order）。
 *
  輸入 ：
  根 = [1, 2, 3, -1, 4, 5, 6]
  圖形：
       1
      / \
     2   3
    /\   /\
  無 4   5 6
  -1 表示 nil，一個正整數表示節點的值（唯一）。
  輸出 (Pre_Order)：
  [1, 2, 4, 3, 5, 6]
 *
 */

// 首先，設計一個枚舉來區分前序、中序、後序
enum OrderType {
    case Pre_Order // 前序
    case In_Order // 中序
    case Post_Order // 後序
}

// 設計一個“節點”物件
class Node {
    var value:Int
    var left:Node?
    var right:Node?
    
    init(value:Int!) {
        self.value = value
    }
}

// 設計一個類，用來：
class Solution {
    
    // 建立二元樹
    func BuildTree(nums: [Int], pos: Int) -> Node? {
        if (pos >= nums.count || nums[pos] == -1) {
            return nil
        }
        let node = Node(value: nums[pos])
        node.left = BuildTree(nums: nums, pos: pos * 2 + 1)
        node.right = BuildTree(nums: nums, pos: pos * 2 + 2)
        return node
    }
    
    // 走訪二元樹
    func Traversal(root: Node!, orderType: OrderType) -> [Int] {
        var result = [Int]()
        switch orderType {
            case .Pre_Order:
                PreOrderTraversal(root: root, result: &result)
            case .In_Order:
                InOrderTraversal(root: root, result: &result)
            case .Post_Order:
                PostOrderTraversal(root: root, result: &result)
        }
        
        return result
    }
    
    // 前序走訪
    func PreOrderTraversal(root: Node!, result: inout [Int]) {
        if (root == nil) {
            return
        }
        result.append(root.value)
        PreOrderTraversal(root: root.left, result: &result)
        PreOrderTraversal(root: root.right, result: &result)
    }
    
    // 中序走訪
    func InOrderTraversal(root: Node!, result: inout [Int]) {
        if (root == nil) {
            return
        }
        InOrderTraversal(root: root.left, result: &result)
        result.append(root.value)
        InOrderTraversal(root: root.right, result: &result)
    }
    
    // 後序走訪
    func PostOrderTraversal(root: Node!, result: inout [Int]) {
        if (root == nil) {
            return
        }
        PostOrderTraversal(root: root.left, result: &result)
        PostOrderTraversal(root: root.right, result: &result)
        result.append(root.value)
    }
}

var solution = Solution()
if let root = solution.BuildTree(nums: [1, 2, 3, -1, 4, 5, 6], pos: 0) {
    print("Pre_Order :")
    print(solution.Traversal(root: root, orderType: OrderType.Pre_Order))
    print("In_Order :")
    print(solution.Traversal(root: root, orderType: OrderType.In_Order))
    print("Post_Order :")
    print(solution.Traversal(root: root, orderType: OrderType.Post_Order))
}
else {
    print(-1)
}

// Output:
Pre_Order :
[1, 2, 4, 3, 5, 6]
In_Order :
[2, 4, 1, 5, 3, 6]
Post_Order :
[4, 2, 5, 6, 3, 1]

if let root = solution.BuildTree(nums: [], pos: 0) {
    print("Pre_Order :")
    print(solution.Traversal(root: root, orderType: OrderType.Pre_Order))
    print("In_Order :")
    print(solution.Traversal(root: root, orderType: OrderType.In_Order))
    print("Post_Order :")
    print(solution.Traversal(root: root, orderType: OrderType.Post_Order))
}
else {
    print(-1)
}

// Output:
-1