leetCodeTree.swift

// Problem 938. Range Sum of BST
// Link: https://leetcode.com/problems/range-sum-of-bst/
// Solution: Depth first search recursive
// Time: O(n), Space: O(n) TODO why?
var sum = 0
func rangeSumBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> Int {
    dfs(root, L, R)
    return sum
}

func dfs(_ root: TreeNode?, _ L: Int, _ R: Int) {
    if let root = root {
        if (L <= root.val && root.val <= R) {
            sum += root.val
        }
        if (root.val < R) {
            dfs(root.right, L, R)
        } 
        if (root.val > L) {
            dfs(root.left, L, R)
        }
    }
}



// Solution 2: Iterative
// Time and Space O(n)
func rangeSumBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> Int {
    if (root == nil) { return 0 }
    var sum = 0;
    var stack = [TreeNode]()
    stack.append(root!)

    while !stack.isEmpty {
        let node = stack.popLast()!
        if(L <= node.val && node.val <= R) {
            sum += node.val
        }
        if(node.val < R && node.right != nil) {
            stack.append(node.right!)
        }
        if(node.val > L && node.left != nil) {
            stack.append(node.left!)
        }
    }

    return sum
}



/****************************************************************/
// Problem 617. Merge Two Binary Trees
// Link: https://leetcode.com/problems/merge-two-binary-trees/
// Solution: recursive
// Time: O(n), Space: O(n)
func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
    guard let t1 = t1 else { return t2 }
    guard let t2 = t2 else { return t1 }
    t1.val += t2.val

    t1.left = mergeTrees(t1.left, t2.left)
    t1.right = mergeTrees(t1.right, t2.right)

    return t1
}



// Solution 2: iterative
// Time: O(n), Space: O(n)
func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
    if t1 == nil { return t2 }
    var stack = [(TreeNode?, TreeNode?)]()
    stack.append((t1, t2))
    while var (node1, node2) = stack.popLast() {
        guard let node2 = node2 else { continue }

        node1!.val += node2.val
        if node1!.left == nil {
            node1!.left = node2.left
        } else {
            stack.append((node1!.left, node2.left))
        }

        if node1!.right == nil {
            node1!.right = node2.right
        } else {
            stack.append((node1!.right, node2.right))
        }
    }
    return t1
}




/****************************************************************/
// Problem 617. Merge Two Binary Trees
// Time: O(n) Space: O(n)
func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    let leftDepth = maxDepth(root.left)
    let rightDepth = maxDepth(root.right)

    return max(leftDepth, rightDepth) + 1
}



/****************************************************************/
// 108. Convert Sorted Array to Binary Search Tree
// Optimal solution NOT MINE
func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
    return sortedArrayToBST(nums, 0, nums.count - 1)
}

private func sortedArrayToBST(_ nums: [Int], _ leftIdx: Int, _ rightIdx: Int) -> TreeNode? {
    guard leftIdx <= rightIdx else {
        return nil
    }

    let mid = (rightIdx - leftIdx) / 2 + leftIdx
    let root = TreeNode(nums[mid])

    root.left = sortedArrayToBST(nums, leftIdx, mid - 1)
    root.right = sortedArrayToBST(nums, mid + 1, rightIdx)

    return root
}



// 590. N-ary Tree Postorder Traversal
// Link: https://leetcode.com/problems/symmetric-tree/solution/
// Time: O(n), Space: O(n)
func isSymmetric(_ root: TreeNode?) -> Bool {
    if root == nil { return true }
    return isSymmetric(root?.left, root?.right)
}

func isSymmetric(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
    if left == nil && right == nil { return true }
    if left == nil || right == nil { return false }

    return left!.val == right!.val
        && isSymmetric(left!.left, right!.right)
        && isSymmetric(left!.right, right!.left)
}



/****************************************************************/
// 199. Binary Tree Right Side View
// Recursive
func rightSideView(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    buildRightSide(root, depth: 0, into: &result)
    return result
}

func buildRightSide(_ node: TreeNode?, depth: Int, into nodes: inout [Int]) {
    guard let node = node else { return }
    if nodes.count == depth {
        nodes.append(node.val)
    } else {
        nodes[depth] = node.val
    }
    buildRightSide(node.left, depth: depth + 1, into: &nodes)
    buildRightSide(node.right, depth: depth + 1, into: &nodes)
}


// Solution 2: Iterative
// O(n) O(n)
func rightSideView(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    var result = [Int]()
    var nodes = [TreeNode]()
    nodes.append(root)
    
    while nodes.count > 0 {
        let size = nodes.count
        
        for i in 0..<size {
            let node = nodes.removeFirst()
            
            if i == size - 1 {
                result.append(node.val)
            }
            if let left = node.left {
                nodes.append(left)
            }
            if let right = node.right {
                nodes.append(right)
            }
        }
    }
    
    return result
}



// 236. Lowest Common Ancestor of a Binary Tree
// Link: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }
    if root === p || root === q {
        return root
    }

    let left = lowestCommonAncestor(root.left, p, q)
    let right = lowestCommonAncestor(root.right, p, q)

    if left != nil && right != nil {
        return root
    } else {
        return left != nil ? left : right
    }
}



// 543. Diameter of Binary Tree
// Link: https://leetcode.com/problems/diameter-of-binary-tree/
func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    let leftDepth = depthOf(root.left)
    let rightDepth = depthOf(root.right)
    print(leftDepth + rightDepth + 1)
    return max(leftDepth + rightDepth,
               diameterOfBinaryTree(root.left),
               diameterOfBinaryTree(root.right))
}

func depthOf(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    return max(depthOf(root.left), depthOf(root.right)) + 1
}



// 437. Path Sum III
// Link: https://leetcode.com/problems/path-sum-iii/submissions/
func pathSum(_ root: TreeNode?, _ sum: Int) -> Int {
    guard let root = root else { return 0 }
    
    return numPathOf(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
}

func numPathOf(_ root: TreeNode?, _ sum: Int) -> Int {
    guard let root = root else { return 0 }
    var count = 0
    let currVal = root.val
    
    if currVal == sum {
        count += 1
    }
    
    return numPathOf(root.left, sum - currVal) + numPathOf(root.right, sum - currVal) + count
}


// https://leetcode.com/problems/validate-binary-search-tree
// Time: O(n), Space: O(n) because trees can be not balanced
func isValidBST(_ root: TreeNode?) -> Bool {
    return isValid(root, nil, nil)
}

func isValid(_ node: TreeNode?, _ min: Int?, _ max: Int?) -> Bool {
    guard let node = node else { return true }

    if min != nil && node.val <= min! { return false }
    if max != nil && node.val >= max! { return false }

    return isValid(node.left, min, node.val) && isValid(node.right, node.val, max)
}


// https://leetcode.com/problems/invert-binary-tree/
// Time: O(n), Space: O(n)
func invertTree(_ root: TreeNode?) -> TreeNode? {
    guard let root = root else { return nil }

    let left = root.left

    root.left = invertTree(root.right)
    root.right = invertTree(left)

    return root
}


// https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
// O(n), O(n)
class Codec {
    let separation = ","
    let null = "null"
    func serialize(_ root: TreeNode?) -> String {
        var result = "["
        buildString(root, &result)
        return result + "]"
    }
    
    func buildString(_ node: TreeNode?, _ str: inout String) {
        if let node = node {
            str += String(node.val) + separation
            buildString(node.left, &str)
            buildString(node.right, &str)
        } else {
            str += "null" + separation
        }
    }
    
    func deserialize(_ data: String) -> TreeNode? {
        let trimmed = data.trimmingCharacters(in: CharacterSet(charactersIn: "[]"))
        var vals = Array(trimmed.components(separatedBy: ",").reversed())
        print(vals)
        
        return buildTree(&vals)
    }
    
    func buildTree(_ vals: inout [String]) -> TreeNode? {
        guard let val = vals.popLast() else { return nil }

        if val == "null" { return nil }
        let node = TreeNode(Int(val) ?? 0)
        node.left = buildTree(&vals)
        node.right = buildTree(&vals)
        return node
    }
}



// Time: O(n), Space: O(n)
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
    var hash = [Int : Int]()
    for (index, num) in inorder.enumerated() {
        hash[num] = index
    }

    return buildTree(0, 0, preorder.count - 1, preorder, hash)
}

func buildTree(_ preStart: Int, _ inStart: Int, _ inEnd: Int, _ preorder: [Int], _ hash: [Int : Int]) -> TreeNode? {
    if inStart > inEnd { return nil }
    let rootVal = preorder[preStart]
    let root = TreeNode(rootVal)
    var index = hash[rootVal]!

    root.left = buildTree(preStart + 1, inStart, index - 1, preorder, hash)
    root.right = buildTree(preStart - inStart + index + 1, index + 1, inEnd, preorder, hash)

    return root
}