LeetCode Binary Tree

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]()) { $0[$1.1] = $1.0 }

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]()) { $0[$1.1] = $1.0 }

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()
}
}

Translated by gpt-3.5-turbo