liuchuo – 第80页 – 我不管，反正我最萌～

[swift] LeetCode 101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.

func isSymmetricTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
    if let p = p, let q = q {
        return p.val == q.val && isSymmetricTree(p.left, q.right) && isSymmetricTree(p.right, q.left)
    } else {
        return p == nil && q == nil
    }
}

func isSymmetric(_ root: TreeNode?) -> Bool {
    return isSymmetricTree(root?.left, root?.right)
}

func isSymmetricTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {

if let p = p, let q = q {

return p.val == q.val && isSymmetricTree(p.left, q.right) && isSymmetricTree(p.right, q.left)

} else {

return p == nil && q == nil

}

func isSymmetric(_ root: TreeNode?) -> Bool {

return isSymmetricTree(root?.left, root?.right)

}

[swift] LeetCode 100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

if let p = p, let q = q {
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
} else {
    return p == nil && q == nil
}

if let p = p, let q = q {

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)

} else {

return p == nil && q == nil

}

[swift] LeetCode 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.

func isValidBST(_ root: TreeNode?) -> Bool {
    return isValidNode(root, Int.min, Int.max)
}

private func isValidNode(_ root: TreeNode?, _ min: Int, _ max: Int) -> Bool {
    guard let p = root else { return true }
    if p.val >= max || p.val <= min { return false }
    return isValidNode(p.left, min, p.val) && isValidNode(p.right, p.val, max)
}

func isValidBST(_ root: TreeNode?) -> Bool {

return isValidNode(root, Int.min, Int.max)

}

private func isValidNode(_ root: TreeNode?, _ min: Int, _ max: Int) -> Bool {

guard let p = root else { return true }

if p.val >= max || p.val <= min { return false }

return isValidNode(p.left, min, p.val) && isValidNode(p.right, p.val, max)

}

[swift] LeetCode 96. Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

func numTrees(_ n: Int) -> Int {
    list = Array(repeating: 1, count: n+1)
    if n >= 2 { list[2] = 2 }
    return g(n)
}

private var list: [Int]!
private func g(_ n: Int) -> Int {
    if  n > 2 && list[n] == 1 {
        list[n] = (1...n).reduce(0) { $0 + f($1, n) }
    }
    return list[n]
}

private func f(_ i: Int, _ n: Int) -> Int {
    return g(i-1) * g(n-i)
}

func numTrees(_ n: Int) -> Int {

list = Array(repeating: 1, count: n+1)

if n >= 2 { list[2] = 2 }

return g(n)

}

private var list: [Int]!

private func g(_ n: Int) -> Int {

if n > 2 && list[n] == 1 {

list[n] = (1...n).reduce(0) { $0 + f($1, n) }

}

return list[n]

}

private func f(_ i: Int, _ n: Int) -> Int {

return g(i-1) * g(n-i)

}

[swift] LeetCode 94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    var list = [Int](), stack = [TreeNode](), p = root

    while p != nil || !stack.isEmpty {
        if let t = p {
            stack.append(t)
            p = t.left
        } else {
            let t = stack.popLast()!
            list.append(t.val)
            p = t.right
        }
    }

    return list
}

func inorderTraversal(_ root: TreeNode?) -> [Int] {

var list = [Int](), stack = [TreeNode](), p = root

while p != nil || !stack.isEmpty {

if let t = p {

stack.append(t)

p = t.left

} else {

let t = stack.popLast()!

list.append(t.val)

p = t.right

}

return list

}

[swift] LeetCode 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

func sortColors(_ nums: inout [Int]) {
    var i0 = 0, i1 = 0, i2 = nums.count-1
    while i1 <= i2 {
        if nums[i1] == 2 {
            nums.swapAt(i1, i2)
            i2 -= 1
        } else if nums[i1] == 0 {
            nums.swapAt(i0, i1)
            i0 += 1; i1 += 1
        } else {
            i1 += 1
        }
    }
}

func sortColors(_ nums: inout [Int]) {

var i0 = 0, i1 = 0, i2 = nums.count-1

while i1 <= i2 {

if nums[i1] == 2 {

nums.swapAt(i1, i2)

i2 -= 1

} else if nums[i1] == 0 {

nums.swapAt(i0, i1)

i0 += 1; i1 += 1

} else {

i1 += 1

}