Swift – 第6页 – 柳婼の blog

[swift] LeetCode 102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }

    var q = [TreeNode](), lists = [[Int]]()
    q.append(root)

    while !q.isEmpty {
        lists.append(q.map { $0.val })

        q = q.reduce([]) { l, t in
            l + [t.left, t.right]
            }.compactMap({$0})
    }

    return lists
}

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

guard let root = root else { return [] }

var q = [TreeNode](), lists = [[Int]]()

q.append(root)

while !q.isEmpty {

lists.append(q.map { $0.val })

q = q.reduce([]) { l, t in

l + [t.left, t.right]

}.compactMap({$0})

}

return lists

}

[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

}