LeetCode Binary Search Tree

发表于 更新于 Disqus： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func isValidBST(_ root: TreeNode?) -> Bool {
        return helper(root, Int.min, Int.max)
    }

    private func helper(_ node: TreeNode?, _ lower: Int, _ upper: Int) -> Bool {
        guard let n = node else { return true }
        if n.val <= lower || n.val >= upper { return false }

        return helper(n.left, lower, n.val) && helper(n.right, n.val, upper)
    }
}

二叉搜索树迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class BSTIterator {

    private var queue = [Int]()
    private func helper(_ root: TreeNode?) {
        guard let root = root else { return }
        helper(root.left)
        queue.append(root.val)
        helper(root.right)
    }

    init(_ root: TreeNode?) {
        helper(root)
    }

    func next() -> Int {
        return queue.removeFirst()
    }

    func hasNext() -> Bool {
        return !queue.isEmpty
    }
}

二叉搜索树中的搜索

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        guard let root = root else { return nil }
        if root.val == val { return root }
        if val < root.val {
            return searchBST(root.left, val)
        } else {
            return searchBST(root.right, val)
        }
    }
}

二叉搜索树中的插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    func insertIntoBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        func insert(_ root: TreeNode? = root, _ val: Int = val) {
            guard let root = root else { return }
            if val < root.val {
                if let l = root.left {
                    insert(l, val)
                } else {
                    root.left = TreeNode(val)
                }
            } else {
                if let r = root.right {
                    insert(r, val)
                } else {
                    root.right = TreeNode(val)
                }
            }
        }
        insert()
        return root ?? TreeNode(val)
    }
}

删除二叉搜索树中的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? {
        guard let root = root else { return nil }
        if root.val == key {
            if root.left != nil && root.right != nil {
                var p = root.right
                while p?.left != nil {  p = p?.left }
                p?.left = root.left
                return root.right
            } else  {
                return root.left != nil ? root.left : root.right
            }
        } else if key < root.val {
            root.left = deleteNode(root.left, key)
        } else {
            root.right = deleteNode(root.right, key)
        }
        return root
    }
}

数据流中的第 K 大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class KthLargest {

    var arr = [Int]()
    var k = 0
    init(_ k: Int, _ nums: [Int]) {
        self.k = k
        for i in nums { add(i) }
    }

    func add(_ val: Int) -> Int {
        if arr.count < k || val > arr.first! {
            var i = 0
            while i < arr.count, val > arr[i] {
                i += 1
            }
            arr.insert(val, at: i)
            if arr.count > k {
                arr.removeFirst()
            }
        }
        return arr.first!
    }

}

二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let root = root, let pv = p?.val, let qv = q?.val else { return nil }
        if root.val >= min(pv, qv) && root.val <= max(pv, qv) { return root }
        return root.val > max(pv, qv) ? lowestCommonAncestor(root.left, p, q) : lowestCommonAncestor(root.right, p, q)
    }
}

存在重复元素 III

1

平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    func isBalanced(_ root: TreeNode?) -> Bool {
        return helper(root).1
    }

    func helper(_ root: TreeNode?) -> (Int, Bool) {
        guard let r = root else { return (0, true) }
        let rl = helper(r.left), rr = helper(r.right)
        return (1 + max(rl.0, rr.0), rl.1 && rr.1 && abs(rl.0 - rr.0) <= 1)
    }
}

将有序数组转换为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        if nums.isEmpty { return nil }
        let n = nums.count, h = n/2, h1 = h+1

        let r = TreeNode(nums[n/2])
        r.left = sortedArrayToBST(Array(nums[0..<h]))
        r.right = sortedArrayToBST(Array(nums[h1...]))
        return r
    }
}