102. Binary Tree Level Order Traversal

a. BFS solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    queue := []*TreeNode{root}
    n := 1
    for n > 0 {
        temp := []int{}
        for n > 0 {
            node := queue[0]
            queue = queue[1:]
            if node != nil {
                temp = append(temp, node.Val)
                queue = append(queue, node.Left)
                queue = append(queue, node.Right)
            }
            n--
        }
        n = len(queue)
        if len(temp) > 0 {
            result = append(result, temp)
        }
    }
    return result
}

b. DFS solution

The idea is passing the level while traversing the tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func dfs(node *TreeNode, level int, result *[][]int) {
    if node != nil {
        if len(*result) < level {
            *result = append(*result, []int{})
        }
        (*result)[level - 1] = append((*result)[level - 1], node.Val)
        dfs(node.Left, level + 1, result)
        dfs(node.Right, level + 1, result)
    }
}

func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    dfs(root, 1, &result)
    return result
}

107. Binary Tree Level Order Traversal II

We just need to reverse the result of BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func levelOrderBottom(root *TreeNode) [][]int {
    result := [][]int{}
    queue := []*TreeNode{root}
    n := 1
    for n > 0 {
        temp := []int{}
        for n > 0 {
            node := queue[0]
            queue = queue[1:]
            if node != nil {
                temp = append(temp, node.Val)
                queue = append(queue, node.Left)
                queue = append(queue, node.Right)
            }
            n--
        }
        n = len(queue)
        if len(temp) > 0 {
            result = append(result, temp)
        }
    }
    for i, j := 0, len(result) - 1; i < j; i, j = i + 1, j - 1 {
        result[i], result[j] = result[j], result[i]
    }
    return result
}

199. Binary Tree Right Side View

We just need to get the right most item (last item) of each layer by using BFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func rightSideView(root *TreeNode) []int {
    result := []int{}
    queue := []*TreeNode{root}
    n := 1
    for n > 0 {
        for i := 0; i < n; i++ {
            node := queue[0]
            queue = queue[1:]
            if node != nil {
                if i == n - 1 {
                    result = append(result, node.Val)
                }
                queue = append(queue, node.Left)
                queue = append(queue, node.Right)
            }
        }
        n = len(queue)
    }
    return result
}

637. Average of Levels in Binary Tree

Get the sum of each level by using BFS or DFS with level information, then claculate the average.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func averageOfLevels(root *TreeNode) []float64 {
    result := []float64{}
    queue := []*TreeNode{root}
    n := 1
    for n > 0 {
        var sum float64 = 0
        item := 0    // Track the not nil item
        for i := 0; i < n; i++ {
            node := queue[0]
            queue = queue[1:]
            if node != nil {
                sum += float64(node.Val)
                item++
                queue = append(queue, node.Left)
                queue = append(queue, node.Right)
            }
        }
        if item > 0 {
            result = append(result, sum / float64(item))   
        }
        n = len(queue)
    }
    return result
}

429. N-ary Tree Level Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func levelOrder(root *Node) [][]int {
    result := [][]int{}
    queue := []*Node{root}
    n := 1
    for n > 0 {
        temp := []int{}
        for n > 0 {
            node := queue[0]
            queue = queue[1:]
            if node != nil {
                temp = append(temp, node.Val)
                for _, child := range node.Children {
                    queue = append(queue, child)
                }
            }
            n--
        }
        if len(temp) > 0 {
            result = append(result, temp)
        }
        n = len(queue)
    }
    return result
}

515. Find Largest Value in Each Tree Row

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func largestValues(root *TreeNode) []int {
    result := []int{}
    if root != nil {
        queue := []*TreeNode{root}
        n := 1
        for n > 0 {
            max := queue[0].Val
            for n > 0 {
                node := queue[0]
                queue = queue[1:]
                if node.Val > max {
                    max = node.Val
                }
                if node.Left != nil {
                    queue = append(queue, node.Left)
                }
                if node.Right != nil {
                    queue = append(queue, node.Right)
                }
                n--
            }
            n = len(queue)
            result = append(result, max)
        }
    }
    return result
}

116. Populating Next Right Pointers in Each Node

a. A naive solution will be using BFS to traverse the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func connect(root *Node) *Node {
    if root != nil {
        queue := []*Node{root}
        n := 1
        for n > 0 {
            for i := 0; i < n; i++ {
                if i > 0 {
                    queue[i - 1].Next = queue[i]
                }
                if queue[i].Left != nil {
                    queue = append(queue, queue[i].Left)
                    queue = append(queue, queue[i].Right)
                }
            }
            queue = queue[n:]
            n = len(queue)
        }
    }
    return root
}

b. DFS solution. Since the given tree is a full complete tree, we can easily use the parent node to get it’s siblings children nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func connect(root *Node) *Node {
    parent := root
    for parent.Left != nil { // Has child node
        current := parent
        for current != nil { // Moving from left to right
            current.Left.Next = current.Right
            if current.Next != nil {
                current.Right.Next = current.Next.Left
            }
            current = current.Next
        }
        parent = parent.Left // Move to the next layer
    }
    return root
}

117. Populating Next Right Pointers in Each Node II

The only difference between this one and the above one is we need to verify the node’s right child before push the into the queue.

a. A naive solution will be using BFS to traverse the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func connect(root *Node) *Node {
    if root != nil {
        queue := []*Node{root}
        n := 1
        for n > 0 {
            for i := 0; i < n; i++ {
                if i > 0 {
                    queue[i - 1].Next = queue[i]
                }
                if queue[i].Left != nil {
                    queue = append(queue, queue[i].Left)
                }
                if queue[i].Right != nil {
                    queue = append(queue, queue[i].Right)
                }
            }
            queue = queue[n:]
            n = len(queue)
        }
    }
    return root
}

b. DFS solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func connect(root *Node) *Node {
    current := root
    for current != nil {
        dummy := &Node{}    // Dummy pointer which points to the first node in current node's child layer
        tail := dummy       // Using tail node to construct a linked list which head is dummy node
        for current != nil {
            if current.Left != nil {
                tail.Next = current.Left
                tail := tail.Next
            }
            if current.Right != nil {
                tail.Next = current.Right
                tail = tail.Next
            }
            current = current.Next
        }
        current = dummy.Next
    }
    return root
}

104. Maximum Depth of Binary Tree

a. BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxDepth(root *TreeNode) int {
    ret := 0
    if root != nil {
        queue := []*TreeNode{root}
        n := len(queue)
        for n > 0 {
            for i := 0; i < n; i++ {
                if node := queue[i]; node != nil {
                    if node.Left != nil {
                        queue = append(queue, node.Left)
                    }
                    if node.Right != nil {
                        queue = append(queue, node.Right)
                    }
                }
            }
            queue = queue[n:]
            n = len(queue)
            ret++
        }
    }
    return ret    
}

b. DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maxDepth(root *TreeNode) int {
    return getDepth(root)
}

func getDepth(node *TreeNode) int {
    if node != nil {
        left := getDepth(node.Left)
        right := getDepth(node.Right)
        if left > right {
            return left + 1
        }
        return right + 1
    }
    return 0
}