BinaryTreeTraversal

https://leetcode.com/problems/binary-tree-inorder-traversal/
https://leetcode.com/problems/binary-tree-inorder-traversal/solution/

func inorderTraversalRecursion(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    func inorder(_ root : TreeNode?){
        if root == nil {
            return
        }
        inorder(root?.left)
        result.append((root?.val)!)
        inorder(root?.right)
    }
    inorder(root)
    return result
}

func inorderTraversalIteration(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    var nodesStack = Array<TreeNode?>()
    var temp = root
    while nil != temp || !nodesStack.isEmpty {
        if nil == temp {
            nodesStack.append(temp)
            temp = temp?.left
        } else {
            temp = nodesStack.popLast()!!
            result.append((temp?.val)!)
            temp = temp?.right
        }
    }
    return result
}

https://leetcode.com/problems/binary-tree-preorder-traversal/

func preorderTraversalRecursion(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    func preorder(_ currentRoot : TreeNode?) {
        if nil == currentRoot {
            return
        }
        result.append((currentRoot?.val)!)
        preorder(currentRoot?.left)
        preorder(currentRoot?.right)
    }
    preorder(root)
    return result
}

func preorderTraversalIteration(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    if nil != root {
        var nodesStack = Array<TreeNode?>()
        nodesStack.append(root)
        while !nodesStack.isEmpty {
            let temp : TreeNode?  = nodesStack.popLast()!
            result.append((temp?.val)!)
            if nil != temp?.right {
                nodesStack.append(temp?.right)
            }
            if nil == temp?.left {
                nodesStack.append(temp?.left)
            }
        }
    }
    return result
}

https://leetcode.com/problems/binary-tree-postorder-traversal/

func preorderTraversalRecursion(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    func preorder(_ currentRoot : TreeNode?) {
        if nil == currentRoot {
            return
        }
        result.append((currentRoot?.val)!)
        preorder(currentRoot?.left)
        preorder(currentRoot?.right)
    }
    preorder(root)
    return result
}

func postorderTraversalIteration(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    if nil != root {
        var nodesStack1 = Array<TreeNode?>()
        var nodesStack2 = Array<TreeNode?>()
        nodesStack1.append(root)
        while !nodesStack1.isEmpty {
            let temp : TreeNode? = nodesStack1.popLast()!
            nodesStack2.append(temp)
            if nil != temp?.left {
                nodesStack1.append(temp?.left)
            }
            if nil != temp?.right {
                nodesStack1.append(temp?.right)
            }
        }
        while !nodesStack2.isEmpty {
            let temp = nodesStack2.popLast()!
            result.append((temp?.val)!)
        }
    }
    return result
}

https://leetcode.com/problems/binary-tree-level-order-traversal/

func levelOrderDFS(_ root: TreeNode?) -> [[Int]] {
    var result = [[Int]]()
    if nil == root {
        return result
    }
    func dfs(node: TreeNode?,level : Int){
        if nil == node {
            return
        }
        if result.count < level + 1 {
            result.append([Int]())
        }
        result[level].append((node?.val)!)
        dfs(node: node?.left, level: level + 1)
        dfs(node: node?.right, level: level + 1)
    }
    dfs(node: root, level: 0)
    return result
}

func levelOrderBFS(_ root: TreeNode?) -> [[Int]] {
    var result = [[Int]]()
    if nil == root {
        return result
    }
    var queue = Array<TreeNode?>()
    queue.append(root)
    while !queue.isEmpty {
        var currentLevel = [Int]()
        let levelSize = queue.count
        for _ in 0..<levelSize {
            let node : TreeNode? = queue.removeFirst()
            currentLevel.append((node?.val)!)
            if nil != node?.left {
                queue.append(node?.left)
            }
            if nil != node?.right {
                queue.append(node?.right)
            }
        }
        result.append(currentLevel)
    }
    return result
}