LeetCode Binary Tree

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

Binary Tree Preorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    // iterative
    func preorderTraversal(_ root: TreeNode?) -> [Int] {
        var ans = [Int
        while let p = stack.popLast() {
            ans.append(p.val)
            if let r = p.right { stack.append(r) }
            if let l = p.left { stack.append(l) }
        }
        return ans
    }

    // recursive
    func preorderTraversal0(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)
    }
}

Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    // iteratively
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var ans = [Int
        while p != nil || !stack.isEmpty {
            while let l = p {
                stack.append(l)
                p = l.left
            }

            if let n = stack.popLast() {
                ans.append(n.val)
                p = n.right
            }
        }
        return ans
    }
}

Binary Tree Postorder Traversal

1
2
3
4
5
6
7
8
class Solution {

    // Recursive
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        return postorderTraversal(root.left) + postorderTraversal(root.right) + [root.val]
    }
}

Binary Tree Level Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        var ans = [[Int]
        helper(root, 0, &ans)
        return ans
    }

    private func helper(_ root: TreeNode?, _ level: Int, _ ans: inout [[Int]]) {
        guard let root = root else { return }
        if level >= ans.count {
            ans.append( [root.val] )
        } else {
            ans[level].append(root.val)
        }

        helper(root.left, level+1, &ans)
        helper(root.right, level+1, &ans)
    }
}

Maximum Depth of Binary Tree

1
2
3
4
5
6
class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {
        guard root != nil else { return 0 }
        return 1 + max(maxDepth(root?.left), maxDepth(root?.right))
    }
}

Symmetric Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func isSymmetric(_ root: TreeNode?) -> Bool {
        return inOrder(root) == inOrder(reverse(root))
    }

    private func reverse(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else { return nil }
        reverse(root.left); reverse(root.right)
        swap(&root.left, &root.right)
        return root
    }

    private func inOrder(_ root: TreeNode?) -> [Int?] {
        return root == nil ? [nil] : [root!.val] + inOrder(root!.left) + inOrder(root!.right)
    }
}

Path Sum

1
2
3
4
5
6
7
class Solution {
    func hasPathSum(_ root: TreeNode?, _ sum: Int) -> Bool {
        guard let root = root else { return false }
        if root.left == nil && root.right == nil && root.val == sum { return true }
        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val)
    }
}

Count Univalue Subtrees

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    func countUnivalSubtrees(_ root: TreeNode?) -> Int {
        isUni(root)
        return num
    }

    private var num = 0
    private func isUni(_ root: TreeNode?) -> Bool {
        guard let root = root else { return true }
        if root.left == nil && root.right == nil {
            num += 1
            return true
        }
        let lv = root.left?.val ?? root.right!.val
        let rv = root.right?.val ?? root.left!.val
        let l = root.left == nil ? true : isUni(root.left)
        let r = root.right == nil ? true : isUni(root.right)

        let ans = l && r && (lv == root.val && rv == root.val)
        if ans { num += 1 }
        return ans
    }
}

Construct Binary Tree from Inorder and Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        let dict = inorder.enumerated().reduce(into: [Int:Int

        func helper(_ inRange: (Int, Int), _ postI: Int) -> TreeNode? {
            if postI < 0 { return nil }
            let v = postorder[postI]
            if let i = dict[v], i >= inRange.0 && i <= inRange.1 {
                let n = TreeNode(v)
                n.left = helper((inRange.0, i-1), postI-1)
                n.right = helper((i+1, inRange.1), postI-1)
                return n
            } else {
                return helper(inRange, postI-1)
            }
        }

        return helper((0, inorder.count-1), postorder.count-1)
    }
}

Construct Binary Tree from Preorder and Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        let dict = inorder.enumerated().reduce(into: [Int: Int

        func helper(_ inRange: (Int, Int), _ preI: Int) -> TreeNode? {
            if preI >= preorder.count { return nil }
            let v = preorder[preI]
            if let i = dict[v], i >= inRange.0 && i <= inRange.1 {
                let n = TreeNode(v)
                n.left = helper((inRange.0, i-1), preI+1)
                n.right = helper((i+1, inRange.1), preI+1)
                return n
            } else {
                return helper(inRange, preI+1)
            }
        }

        return helper((0, inorder.count-1), 0)
    }
}

Populating Next Right Pointers in Each Node

1
2
3
4
5
6
7
8
9
10
class Solution {
    func connect(_ root: Node?) -> Node? {
        guard let root = root else { return nil }
        root.left?.next = root.right
        root.right?.next = root.next?.left
        connect(root.left)
        connect(root.right)
        return root
    }
}

Populating Next Right Pointers in Each Node II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func connect(_ root: Node?) -> Node? {
        var nodes = [[Node]
        helper(root, 0, &nodes)

        for i in 0..<nodes.count {
            for j in 0..<(nodes[i].count-1) {
                nodes[i][j].next = nodes[i][j+1]
            }
        }
        return root
    }

    private func helper(_ root: Node?, _ level: Int, _ nodes: inout [[Node]]) {
        guard let root = root else { return }
        level < nodes.count ? nodes[level].append(root) : nodes.append([root])
        helper(root.left, level+1, &nodes)
        helper(root.right, level+1, &nodes)
    }
}

Lowest Common Ancestor of a Binary Tree

1
2
3
4
5
6
7
8
class Solution {
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let root = root, let p = p, let q = q else { return nil }
        let l = lowestCommonAncestor(root.left, p, q), r = lowestCommonAncestor(root.right, p, q)
        if root.val == p.val || root.val == q.val || (l != nil && r != nil) { return root }
        return l ?? r
    }
}

Serialize and Deserialize Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Codec {
    func serialize(_ root: TreeNode?) -> String {
        guard let root = root else { return "#" }
        return "\(root.val),\(serialize(root.left)),\(serialize(root.right))"
    }

    func deserialize(_ data: String) -> TreeNode? {
        let vals = data.split(separator: ",")
        var i = 0
        func helper() -> TreeNode? {
            guard i < vals.count, let v = Int(vals[i]) else { return nil }
            let n = TreeNode(v)
            i += 1; n.left = helper()
            i += 1; n.right = helper()
            return n
        }
        return helper()
    }
}