吹拉弹唱


  • Home
  • Archive
  • Categories
  • Tags
  • Books
  •  

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo

Code - Tree

Posted at 2022-05-15Updated at 2022-05-15 interview  interview algorithm 

  • Basics
    • Tree
    • Binary Tree
    • Full Binary Tree
    • Complete Binary Tree
    • Binary Search Tree
    • Balanced Search Tree
    • AVL Tree
    • Red–Black Tree
    • B-Tree
    • B+Tree
    • B*Tree
  • LeetCode
    • 144. Binary Tree Preorder Traversal
    • 589. N-ary Tree Preorder Traversal
    • 145. Binary Tree Postorder Traversal
    • 590. N-ary Tree Postorder Traversal
    • 94. Binary Tree Inorder Traversal
    • 102. Binary Tree Level Order Traversal
    • 107. Binary Tree Level Order Traversal II
    • 199. Binary Tree Right Side View
    • 637. Average of Levels in Binary Tree
    • 429. N-ary Tree Level Order Traversal
    • 114. Flatten Binary Tree to Linked List
    • 226. Invert Binary Tree
    • 101. Symmetric Tree
    • 104. Maximum Depth of Binary Tree
    • 559. Maximum Depth of N-ary Tree
    • 111. Minimum Depth of Binary Tree
    • 222. Count Complete Tree Nodes
    • 110. Balanced Binary Tree
    • 257. Binary Tree Paths
    • 100. Same Tree
    • 404. Sum of Left Leaves
    • 513. Find Bottom Left Tree Value
    • 112. Path Sum
    • 113. Path Sum II
    • 437. Path Sum III
    • 106. Construct Binary Tree from Inorder and Postorder Traversal
    • 105. Construct Binary Tree from Preorder and Inorder Traversal
    • 654. Maximum Binary Tree
    • 617. Merge Two Binary Trees
    • 700. Search in a Binary Search Tree
    • 98. Validate Binary Search Tree
    • 530. Minimum Absolute Difference in BST
    • 501. Find Mode in Binary Search Tree
    • 236. Lowest Common Ancestor of a Binary Tree
    • 235. Lowest Common Ancestor of a Binary Search Tree
    • 1644. Lowest Common Ancestor of a Binary Tree II
    • 1650. Lowest Common Ancestor of a Binary Tree III
    • 1676. Lowest Common Ancestor of a Binary Tree IV
    • 701. Insert into a Binary Search Tree
    • 450. Delete Node in a BST
    • 669. Trim a Binary Search Tree
    • 108. Convert Sorted Array to Binary Search Tree
    • 109. Convert Sorted List to Binary Search Tree
    • 1008. Construct Binary Search Tree from Preorder Traversal
    • 449. Serialize and Deserialize BST
    • 538. Convert BST to Greater Tree
    • 99. Recover Binary Search Tree
    • 103. Binary Tree Zigzag Level Order Traversal
    • 1022. Sum of Root To Leaf Binary Numbers
    • 116. Populating Next Right Pointers in Each Node
    • 117. Populating Next Right Pointers in Each Node II
    • 449. Serialize and Deserialize BST
    • 297. Serialize and Deserialize Binary Tree
    • 652. Find Duplicate Subtrees
    • 606. Construct String from Binary Tree
    • 124. Binary Tree Maximum Path Sum
    • 129. Sum Root to Leaf Numbers
    • 988. Smallest String Starting From Leaf
    • 230. Kth Smallest Element in a BST
    • 671. Second Minimum Node In a Binary Tree

# Basics

1
2
3
4
5
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

# Tree

A directional acyclic linear data structure in which each node can point to multiple nodes and only one node can point to self.

# Binary Tree

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

# Full Binary Tree

A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children.

# Complete Binary Tree

A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.

# Binary Search Tree

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree.

  • pros: No need to adjust the structure when inserting data.
  • cons: The performance can be easily affected by the order of data insertion. The worst case is sequential insertion, which degenerates into a linked list.

# Balanced Search Tree

A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

# AVL Tree

An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree (BST). It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

  • pros: More balanced compared to binary search tree. The performance is still good enough in extreme cases.
  • cons: In the case of a similar read-write ratio, there are too many rotation operations.

# Red–Black Tree

A red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing “color” (“red” or “black”), used to ensure that the tree remains balanced during insertions and deletions.

  1. Every node has a colour either red or black.
  2. The root of the tree is always black.
  3. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
  4. Every path from a node (including root) to any of its descendants NULL nodes has the same number of black nodes.
  5. All leaf nodes are black nodes.
  • pros: The writing performance is much higher.
  • cons: The searching performance is not as good as AVL tree, because the height difference of the child tree is 1 more than AVL, the worst case will have an extra comparison.

# B-Tree

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children.

M-ary search tree. Used for data indexing, the child node stores pointers and data chunks。the tree structure is maintained by splitting operations.

# B+Tree

A B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.

A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves.

# B*Tree

B*-tree of order m is a search tree that is either empty or that satisfies three properties:

  1. The root node has minimum two and maximum 2 floor ((2m-2)/3) +1 children
  2. Other internal nodes have the minimum floor ((2m-1)/3) and maximum m children
  3. All external nodes are on the same level.

# LeetCode

# 144. Binary Tree Preorder Traversal

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }
    result = append(result, root.Val)
    result = append(result, preorderTraversal(root.Left)...)
    result = append(result, preorderTraversal(root.Right)...)
    return result
}

Iteration

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
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    result := []int{}
    if root != nil {
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
            stack = append(stack, node)
            stack = append(stack, nil)
        } else {
            node = stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            result = append(result, node.Val)
        }
    }
    return result
}

# 589. N-ary Tree Preorder Traversal

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func preorder(root *Node) []int {
    result := []int{}
    if root == nil { return result }
    result = append(result, root.Val)
    for _, child := range root.Children {
        result = append(result, preorder(child)...)
    }
    return result    
}

# 145. Binary Tree Postorder Traversal

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }
    result = append(result, postorderTraversal(root.Left)...)
    result = append(result, postorderTraversal(root.Right)...)
    result = append(result, root.Val)
    return result    
}

Iteration

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
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    result := []int{}
    if root != nil {
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            stack = append(stack, node)
            stack = append(stack, nil)
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
        } else {
            node = stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            result = append(result, node.Val)
        }
    }
    return result 
}

# 590. N-ary Tree Postorder Traversal

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func postorder(root *Node) []int {
    result := []int{}
    if root == nil { return result }
    for _, child := range root.Children {
        result = append(result, postorder(child)...)
    }
    result = append(result, root.Val)
    return result
}

# 94. Binary Tree Inorder Traversal

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }
    result = append(result, inorderTraversal(root.Left)...)
    result = append(result, root.Val)
    result = append(result, inorderTraversal(root.Right)...)
    return result        
}

Iteration

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
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    result := []int{}
    if root != nil {
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            stack = append(stack, node)
            stack = append(stack, nil)
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
        } else {
            node = stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            result = append(result, node.Val)
        }
    }
    return result    
}

# 102. Binary Tree Level Order Traversal

leetcode

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
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    queue := []*TreeNode{}
    result := [][]int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        vec := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            vec = append(vec, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, vec)
    }
    return result
}

# 107. Binary Tree Level Order Traversal II

leetcode

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
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
    queue := []*TreeNode{}
    result := [][]int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        vec := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            vec = append(vec, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append([][]int{vec}, result...)
    }
    return result
}

Or

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
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
    queue := []*TreeNode{}
    result := [][]int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        vec := []int{}
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            vec = append(vec, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, vec)
    }
    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

leetcode

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
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    queue := []*TreeNode{}
    result := []int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == size - 1 {
                result = append(result, node.Val)
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return result
}

# 637. Average of Levels in Binary Tree

leetcode

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
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func averageOfLevels(root *TreeNode) []float64 {
    queue := []*TreeNode{}
    result := []float64{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        sum := 0
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            sum += node.Val
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, float64(sum) / float64(size))
    }
    return result  
}

# 429. N-ary Tree Level Order Traversal

leetcode

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
28
29
30
31
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func levelOrder(root *Node) [][]int {
    queue := []*Node{}
    result := [][]int{}
    if root != nil {
        queue = append(queue, root)
    }
    for len(queue) > 0 {
        size := len(queue)
        vec := make([]int, 0, size)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            vec = append(vec, node.Val)
            for _, child := range node.Children {
                if child != nil {
                    queue = append(queue, child)
                }
            }
        }
        result = append(result, vec)
    }
    return result     
}

# 114. Flatten Binary Tree to Linked List

leetcode

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
28
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode)  {
    stack := []*TreeNode{}
    list := []*TreeNode{}
    node := root
    for node != nil || len(stack) > 0 {
        for node != nil {
            list = append(list, node)
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack) - 1]
        node = node.Right
        stack = stack[:len(stack) - 1]
    }

    for i := 1; i < len(list); i++ {
        prev, curr := list[i-1], list[i]
        prev.Left, prev.Right = nil, curr
    }    
}

# 226. Invert Binary Tree

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

Iteration

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    stack := []*TreeNode{}
    stack = append(stack, root)
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        node.Left, node.Right = node.Right, node.Left
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
    }
    return root
}

Level Order

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
28
29
30
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    queue := []*TreeNode{}
    if root == nil {
        return root
    }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            node.Left, node.Right = node.Right, node.Left
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return root
}

# 101. Symmetric Tree

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func compare(left *TreeNode, right *TreeNode) bool {
    if right != nil && left == nil { return false }
    if right == nil && left != nil { return false }
    if right == nil && left == nil { return true }
    if right.Val != left.Val { return false }

    outside := compare(left.Left, right.Right)
    inside := compare(left.Right, right.Left)
    return outside && inside
}

func isSymmetric(root *TreeNode) bool {
    if root == nil { return true }
    return compare(root.Left, root.Right)
}

Iteration

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
28
29
30
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil { return true }
    queue := []*TreeNode{}
    queue = append(queue, root.Left)
    queue = append(queue, root.Right)

    for len(queue) > 0 {
        left := queue[0]; queue = queue[1:]
        right := queue[0]; queue = queue[1:]
        if left == nil && right == nil {
            continue
        }
        if left == nil || right == nil || left.Val != right.Val {
            return false
        }
        queue = append(queue, left.Left)
        queue = append(queue, right.Right)
        queue = append(queue, left.Right)
        queue = append(queue, right.Left)
    }
    return true
}

# 104. Maximum Depth of Binary Tree

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Iteration

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
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxDepth(root *Node) int {
    queue := []*Node{}
    depth := 0
    if root == nil { return depth }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        depth++
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            queue = append(queue, node.Left)
            queue = append(queue, node.Right)
        }
    }
    return depth
}

# 559. Maximum Depth of N-ary Tree

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }
    max := 0
    for _, child := range root.Children {
        depth := maxDepth(child)
        if depth > max {
            max = depth
        }
    }
    return 1 + max
}

Iteration

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
28
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func maxDepth(root *Node) int {
    queue := []*Node{}
    depth := 0
    if root == nil { return depth }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        depth++
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            for _, n := range node.Children {
                if n != nil {
                    queue = append(queue, n)
                }
            }
        }
    }
    return depth
}

# 111. Minimum Depth of Binary Tree

leetcode

Recursion

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
28
29
30
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil { return 0 }
    leftDepth := minDepth(root.Left)
    rightDepth := minDepth(root.Right)

    if root.Left == nil && root.Right != nil {
        return 1 + rightDepth
    }

    if root.Right == nil && root.Left != nil {
        return 1 + leftDepth
    }

    return 1 + min(leftDepth, rightDepth)    
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

Iteration

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
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    queue := []*TreeNode{}
    depth := 0
    if root == nil { return depth }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        depth++
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Left == nil && node.Right == nil {
                return depth
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return depth
}

# 222. Count Complete Tree Nodes

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
    if root == nil { return 0 }
    return 1 + countNodes(root.Left) + countNodes(root.Right)
}

Iteration

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
28
29
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
    queue := []*TreeNode{}
    count := 0
    if root == nil { return count }
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            count++
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return count
}

# 110. Balanced Binary Tree

leetcode

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
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func min(x, y int) int {
    if x > y { return x }
    return y
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func depth(node *TreeNode) int {
    if node == nil { return 0 }
    leftDepth := depth(node.Left)
    if leftDepth < 0 { return -1 }
    rightDepth := depth(node.Right)
    if rightDepth < 0 { return -1 }
    if abs(leftDepth - rightDepth) > 1 {
        return -1
    }
    return 1 + min(leftDepth, rightDepth)
}

func isBalanced(root *TreeNode) bool {
    return depth(root) >= 0
}

# 257. Binary Tree Paths

leetcode

Simple preorder 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
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func binaryTreePaths(root *TreeNode) []string {
    if root == nil {
        return []string{}
    }
    return path(root, "")
}

func path(node *TreeNode, pathStr string) []string{
    results := []string{}
    pathStr += fmt.Sprintf("%d", node.Val)
    if node.Left == nil && node.Right == nil {
        return []string{pathStr}
    }
    pathStr += "->"
    if node.Left != nil {
        results = append(results, path(node.Left, pathStr)...)
    }
    if node.Right != nil {
        results = append(results, path(node.Right, pathStr)...)
    }
    return results
}

# 100. Same Tree

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil && q != nil || p != nil && q == nil {
        return false
    }
    if p != nil && q != nil && p.Val != q.Val {
        return false
    }
    if !isSameTree(p.Left, q.Left) || !isSameTree(p.Right, q.Right) {
        return false
    }
    return true
}

Iteration

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
28
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
    queue := []*TreeNode{}
    queue = append(queue, p)
    queue = append(queue, q)
    for len(queue) > 0 {
        left := queue[0]; queue = queue[1:]
        right := queue[0]; queue = queue[1:]
        if left == nil && right == nil {
            continue
        }
        if left == nil || right == nil || left.Val != right.Val {
            return false
        }
        queue = append(queue, left.Left)
        queue = append(queue, right.Left)
        queue = append(queue, left.Right)
        queue = append(queue, right.Right)
    }
    return true
}

# 404. Sum of Left Leaves

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil { return 0 }
    sum := 0
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        sum = root.Left.Val
    }
    return sum + sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)    
}

# 513. Find Bottom Left Tree Value

leetcode

Layer 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
25
26
27
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    queue := []*TreeNode{root}
    result := 0
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == 0 { result = node.Val }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return result
}

# 112. Path Sum

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil { return false }
    if root.Left == nil && root.Right == nil && root.Val == targetSum {
        return true
    }
    nextSum := targetSum - root.Val
    return hasPathSum(root.Left, nextSum) || hasPathSum(root.Right, nextSum)
}

# 113. Path Sum II

leetcode

Recursion

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
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func traverse(root *TreeNode, targetSum int, res *[][]int, path[]int) {
    path = append(path, root.Val)
    nextSum := targetSum - root.Val
    if root.Left == nil && root.Right == nil {
        if nextSum == 0 {
            tmp := make([]int, len(path))
            copy(tmp, path)
            *res = append(*res, tmp)
        }
        return
    }

    if root.Left != nil {
        traverse(root.Left, nextSum, res, path)
    }
    if root.Right != nil {
        traverse(root.Right, nextSum, res, path)
    }
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    result := [][]int{}
    path := []int{}
    if root == nil { return result }
    traverse(root, targetSum, &result, path)
    return result
}

# 437. Path Sum III

leetcode

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
    if root == nil {
        return 0
    }
    return pathSumFrom(root, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}

func pathSumFrom(node *TreeNode, currentSum int) int {
    if node == nil {
        return 0
    }
    sum := 0
    if node.Val == currentSum {
        sum += 1
    }
    nextSum := currentSum - node.Val
    return sum + pathSumFrom(node.Left, nextSum) + pathSumFrom(node.Right, nextSum)
}

# 106. Construct Binary Tree from Inorder and Postorder Traversal

leetcode

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
28
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func traverse(inorder []int, postorder []int, inStart, inEnd, poStart, poEnd int) *TreeNode {
    if poStart == poEnd { return nil }
    rootVal := postorder[poEnd - 1]
    root := &TreeNode{Val: rootVal}
    if poEnd - poStart == 1 { return root }

    var inMid int
    for inMid = inStart; inMid < inEnd; inMid++ {
        if inorder[inMid] == rootVal { break }
    }

    poMid := poStart + inMid - inStart
    root.Left = traverse(inorder, postorder, inStart, inMid, poStart, poMid)
    root.Right = traverse(inorder, postorder, inMid + 1, inEnd, poMid, poEnd - 1)
    return root
}

func buildTree(inorder []int, postorder []int) *TreeNode {
    return traverse(inorder, postorder, 0, len(inorder), 0, len(postorder))
}

# 105. Construct Binary Tree from Preorder and Inorder Traversal

leetcode

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
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func traverse(preorder []int, inorder []int, prStart, prEnd, inStart, inEnd int) *TreeNode {
    // fmt.Printf("%v %v %v %v\n", prStart, prEnd, inStart, inEnd)
    if prStart == prEnd {
        return nil
    }
    val := preorder[prStart]
    root := &TreeNode{Val: val}
    if prEnd - prStart == 1 {
        return root
    }
    
    var inMid int
    for inMid = inStart; inMid < inEnd; inMid++{
        if inorder[inMid] == val {
            break
        }
    }
    
    prMid := prStart + 1 + inMid - inStart
    root.Left = traverse(preorder, inorder, prStart+1, prMid, inStart, inMid)
    root.Right = traverse(preorder, inorder, prMid, prEnd, inMid+1, inEnd)
    return root
}

func buildTree(preorder []int, inorder []int) *TreeNode {
    return traverse(preorder, inorder, 0, len(preorder), 0, len(inorder))
}

More concise using slice.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    // fmt.Printf("%v | %v \n", preorder, inorder)
    if len(preorder) == 0 { return nil }
    rootVal := preorder[0]
    root := &TreeNode{Val: rootVal}
    if len(preorder) == 1 { return root }

    var inMid int
    for inMid = 0; inMid < len(inorder); inMid++ {
        if inorder[inMid] == rootVal { break }
    }

    root.Left = buildTree(preorder[1:1+inMid], inorder[:inMid])
    root.Right = buildTree(preorder[1+inMid:], inorder[inMid+1:])
    return root
}

# 654. Maximum Binary Tree

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 { return nil }
    max := nums[0]
    index := 0
    for i, v := range nums {
        if v > max { 
            max = v
            index = i
        }
    }
    root := &TreeNode{Val: max}
    root.Left = constructMaximumBinaryTree(nums[:index])
    root.Right = constructMaximumBinaryTree(nums[index+1:])
    return root
}

Monotonic Stack

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
28
29
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 { return nil }
    stack := []*TreeNode{}
    var last *TreeNode
    for _, num := range nums {
        for len(stack) > 0 && stack[len(stack)-1].Val < num {
            last = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        node := &TreeNode{Val: num}
        if len(stack) > 0 {
            stack[len(stack)-1].Right = node
        }
        if last != nil {
            node.Left = last
        }
        stack = append(stack, node)
        last = nil
    }
    return stack[0]
}

# 617. Merge Two Binary Trees

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil && root2 == nil {
        return nil
    }
    if root1 == nil && root2 != nil {
        return root2
    }
    if root1 != nil && root2 == nil {
        return root1
    }
    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

# 700. Search in a Binary Search Tree

leetcode

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil { return nil }
    if root.Val > val { return searchBST(root.Left, val) }
    if root.Val < val { return searchBST(root.Right, val) }
    return root
}

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil {
        if root.Val > val { 
            root = root.Left
        } else if root.Val < val {
            root = root.Right
        } else {
            return root
        }
    }
    return nil
}

# 98. Validate Binary Search Tree

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return helper(root, math.MinInt64, math.MaxInt64)
}

func helper(root *TreeNode, lower, upper int) bool {
    if root == nil {
        return true
    }
    if root.Val <= lower || root.Val >= upper {
        return false
    }
    return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}

# 530. Minimum Absolute Difference in BST

leetcode

Inorder 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
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type Searcher struct {
    min int
    last int
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func (s *Searcher)traverse(root *TreeNode) {
    if root == nil { return }
    s.traverse(root.Left)
    val := abs(root.Val - s.last)
    if val < s.min {
        s.min = val
    }
    s.last = root.Val
    s.traverse(root.Right)
}

func getMinimumDifference(root *TreeNode) int {
    s := Searcher{math.MaxInt64, math.MaxInt64}
    s.traverse(root)
    return s.min
}

Interval

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
    return traverse(root, math.MinInt32, math.MaxInt32)
}

func traverse(node *TreeNode, lo, hi int) int {
    if node == nil {
        return hi - lo
    }
    left := traverse(node.Left, lo, node.Val)
    right := traverse(node.Right, node.Val, hi)
    return min(left, right)
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 501. Find Mode in Binary Search Tree

leetcode

Inorder 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type Searcher struct {
    Last int
    Count int
    MaxCount int
    Modes []int
}

func (s *Searcher)traverse(root *TreeNode) {
    if root == nil { return }
    s.traverse(root.Left)
    if root.Val == s.Last {
        s.Count++
    } else {
        s.Last = root.Val
        s.Count = 1
    }
    if s.Count > s.MaxCount {
        s.Modes = nil
        s.Modes = append(s.Modes, root.Val)
        s.MaxCount = s.Count
    } else if s.Count == s.MaxCount {
        s.Modes = append(s.Modes, root.Val)
    }
    s.traverse(root.Right)
}

func findMode(root *TreeNode) []int {
    s := Searcher{
        Last: 0,
        Count: 0,
        MaxCount: 0,
    }
    s.traverse(root)
    return s.Modes
}

Hash Table

But with extra space.

# 236. Lowest Common Ancestor of a Binary Tree

leetcode

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
28
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
     if root == nil {
         return nil
     }
     if root.Val == p.Val || root.Val == q.Val {
         return root
     }
     left := lowestCommonAncestor(root.Left, p, q)
     right := lowestCommonAncestor(root.Right, p, q)
     if left != nil && right != nil {
         return root
     }
     if left == nil && right != nil {
         return right
     }
     if left != nil && right == nil {
         return left
     }
     return nil
}

# 235. Lowest Common Ancestor of a Binary Search Tree

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }
    if p.Val > root.Val && q.Val > root.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }
    return root
}

# 1644. Lowest Common Ancestor of a Binary Tree II

chowdera

This similar to 236, except we have to

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 var findp, findq bool

 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    findp, findq = false, false
    ans := lowestCommonAncestor1(root, p, q)
    if findp && findq {
        return ans
    }
    return nil
 }

 func lowestCommonAncestor1(root, p, q *TreeNode) *TreeNode {
     if root == nil {
         return nil
     }
     if root.Val == p.Val {
        findp = true
     }
     if root.Val == q.Val {
        findq = true
     }
     left := lowestCommonAncestor(root.Left, p, q)
     right := lowestCommonAncestor(root.Right, p, q)
     if root.Val == p.Val || root.Val == q.Val {
        return root
     }
     if left != nil && right != nil {
         return root
     }
     if left == nil && right != nil {
         return right
     }
     if left != nil && right == nil {
         return left
     }
     return nil
}

# 1650. Lowest Common Ancestor of a Binary Tree III

chowdera

The problem is equivalent to 160. Using a hash map to stop early.

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 *     Parent *TreeNode
 * }
 */
 func lowestCommonAncestor(p, q *TreeNode) *TreeNode {
     if p == nil || q == nil {
         return nil
     }
     d := make(map[*TreeNode]struct{})
     for p != nil {
         d[p] = struct{}{}
         p = p.Next
     }
     for q != nil {
         if p, exists := d[q]; exists {
             return p
         }
         q = q.Next
     }
     return nil
 }

# 1676. Lowest Common Ancestor of a Binary Tree IV

leetcode

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
28
29
30
31
32
33
34
35
36
37
var set map[int]strutct{}

func lowestCommonAncestor(root *TreeNode, nodes []*TreeNode) *TreeNode {
    set = map[int]struct{}{}
    for i := range nodes {
        set[nodes[i].Val] = struct{}{}
    }
    var ans *TreeNode
    for i := range nodes {
        ans = lowestCommonAncestor2(root, ans, nodes[i])
    }
    return ans
}

func lowestCommonAncestor2(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    if root.Val == p.Val || root.Val == q.Val {
        return root
    }
    if _, exists := set[root.Val]; exists {
        return root
    }
    l := lowestCommonAncestor2(root.Left, p, q)
    r := lowestCommonAncestor2(root.Right, p, q)
    if l != nil && r != nil {
        return root
    }
    if l != nil && r == nil {
        return l
    }
    if l != nil && r != nil {
        return r
    }
    return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*> &nodes) {

    for(auto n : nodes)
        s.insert(n);
    TreeNode* ans = NULL;
    for(auto n : nodes)
        ans = lowestCommonAncestor(root, ans, n);
    return ans;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{

    if(!root || p==root || q==root || s.count(root)) return root;
    auto l = lowestCommonAncestor(root->left, p, q);
    auto r = lowestCommonAncestor(root->right, p, q);
    if(l&&r) return root;
    return l ? l : r;
}

# 701. Insert into a Binary Search Tree

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    if val < root.Val {
        root.Left = insertIntoBST(root.Left, val)
    }
    if val > root.Val {
        root.Right = insertIntoBST(root.Right, val)
    }
    return root
}

# 450. Delete Node in a BST

leetcode

  1. Cannot find in tree.
  2. If the node is leaf, just delete it. parent.left = null
  3. If the right child is null, parent.left = node.left
  4. If the left child is null, parent.left = node.right
  5. If both the left and right child are not null, there two methods:
    1. substitute with the least node in right sub-tree, this node is still larger than any node in the left sub-tree. How to find that node? This node is the most left node of right sub-tree.
    2. hang the left sub-tree to the most left node of right sub-tree, this is equivalent to 3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil { return root }
    if root.Val == key {
        if root.Right == nil {
            return root.Left
        }
        cur := root.Right
        for cur.Left != nil {
            cur = cur.Left
        }
        root.Val, cur.Val = cur.Val, root.Val
    }
    root.Left = deleteNode(root.Left, key)
    root.Right = deleteNode(root.Right, key)
    return root    
}

# 669. Trim a Binary Search Tree

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil { return root }
    if root.Val < low {
        return trimBST(root.Right, low, high)
    }
    if root.Val > high {
        return trimBST(root.Left, low, high)
    }
    root.Left = trimBST(root.Left, low, high)
    root.Right = trimBST(root.Right, low, high)
    return root    
}

# 108. Convert Sorted Array to Binary Search Tree

leetcode

Keep dividing the num array into two equal parts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 { return nil }
    mid := len(nums) / 2
    root := &TreeNode{Val: nums[mid]}
    root.Left = sortedArrayToBST(nums[:mid])
    root.Right = sortedArrayToBST(nums[mid+1:])
    return root    
}

# 109. Convert Sorted List to Binary Search Tree

leetcode

108

Converted to 108. And the time complexity is O(N) and the space complexity is O(N).

Divide Conquer

TC O(N) SC O(logN)

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
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedListToBST(head *ListNode) *TreeNode {
    if head == nil {
        return nil
    }
    if head.Next == nil {
        return &TreeNode{Val: head.Val}
    }
    slow, fast := head, head.Next.Next
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    mid := slow.Next
    slow.Next = nil
    root := &TreeNode{Val: mid.Val}
    root.Left = sortedListToBST(head)
    root.Right = sortedListToBST(mid.Next)
    return root
}

# 1008. Construct Binary Search Tree from Preorder Traversal

leetcode

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstFromPreorder(preorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    root := &TreeNode{Val: preorder[0]}
    if len(preorder) == 1 {
        return root
    }
    var mid int
    for mid = 1; mid < len(preorder); mid++ {
        if preorder[mid] > preorder[0] {
            break
        }
    }
    root.Left = bstFromPreorder(preorder[1:mid])
    root.Right = bstFromPreorder(preorder[mid:])
    return root
}

# 449. Serialize and Deserialize BST

Use preorder traversal

1

# 538. Convert BST to Greater Tree

leetcode

Simply use inverse inorder traversal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func traverse(root *TreeNode, val int) int {
    if root == nil { return val }
    val = traverse(root.Right, val)
    root.Val += val
    val = root.Val
    val = traverse(root.Left, val)
    return val
}

func convertBST(root *TreeNode) *TreeNode {
    traverse(root, 0)
    return root
}

# 99. Recover Binary Search Tree

leetcode

The inorder traversal of binary search tree is monotonically increasing. Since there are only two nodes were swapped, they must be adjacent elements. Find out these two elements and swap them.

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
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var first, second, prev *TreeNode

func recoverTree(root *TreeNode)  {
    first = nil
    second = nil
    prev = &TreeNode{Val: math.MinInt32}
    traverse(root)
    first.Val, second.Val = second.Val, first.Val
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    
    traverse(root.Left)
    
    if first == nil && prev.Val > root.Val {
        first = prev
    }
    
    if first != nil && prev.Val > root.Val {
        second = root
    }
    
    prev = root
    
    traverse(root.Right)
}

# 103. Binary Tree Zigzag Level Order Traversal

leetcode

Use a new queue to store the nodes of the next layer.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    zig := true
    queue := []*TreeNode{root}
    res := [][]int{}
    for len(queue) > 0 {
        size := len(queue)
        vec := make([]int, 0, size)
        nqueue := []*TreeNode{}
        for i := 0; i < size; i++ {
            var val int
            if zig {
                val = queue[i].Val 
            } else {
                val = queue[size-1-i].Val
            }
            vec = append(vec, val)
            node := queue[i]
            
            if node.Left != nil {
                nqueue = append(nqueue, node.Left)
            }
            if node.Right != nil {
                nqueue = append(nqueue, node.Right)
            }
        }
        queue = nqueue
        res = append(res, vec)
        zig = !zig
    }
    return res
}

# 1022. Sum of Root To Leaf Binary Numbers

leetcode

Using <<.

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    if root == nil { return 0 }
    return traverse(root, 0)
}

func traverse(root *TreeNode, value int) int {
    if root.Left == nil && root.Right == nil {
        return value << 1 + root.Val
    }
    sum := 0
    nextValue := value << 1 + root.Val
    if root.Left != nil {
        sum += traverse(root.Left, nextValue)
    }
    if root.Right != nil {
        sum += traverse(root.Right, nextValue)
    }
    return sum
}

# 116. Populating Next Right Pointers in Each Node

leetcode

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
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    queue := []*Node{root}
    for len(queue) > 0 {
        size := len(queue)
        var prev *Node
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if prev != nil && i < size {
                prev.Next = node
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
            prev = node
        }
    }
    return root
}

O(1) Space

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
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    level_start := root
    for level_start != nil {
        cur := level_start
        for cur != nil {
            if cur.Left != nil {
                cur.Left.Next = cur.Right
            }
            if cur.Right != nil && cur.Next != nil {
                cur.Right.Next = cur.Next.Left
            }
            cur = cur.Next
        }
        level_start = level_start.Left
    }
    return root
}

# 117. Populating Next Right Pointers in Each Node II

leetcode

Level Order Traversal Same as 116.

O(1) Space

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
28
29
30
31
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    cur := &Node{Val: 0}
    dummy := cur
    level := root
    for level != nil {
        cur.Next = level.Left
        if cur.Next != nil {
            cur = cur.Next
        }
        cur.Next = level.Right
        if cur.Next != nil {
            cur = cur.Next
        }
        level = level.Next
        if level == nil {
            cur = dummy
            level = dummy.Next
        }
    }
    return root
}

# 449. Serialize and Deserialize BST

leetcode

Borrow from 144 and 1008.

Be careful with make([]int, 0, 0), this will return a []int{0}

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
    
}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return ""
    }
    result := preorderTraversal(root)
    resultStr := make([]string, 0, len(result))
    for i := range result {
        resultStr = append(resultStr, strconv.Itoa(result[i]))
    }
    return strings.Join(resultStr, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    if data == "" {
        return nil
    }
    resultStr := strings.Split(data, ",")
    result := make([]int, 0, len(resultStr))
    for i := range resultStr {
        num, _ := strconv.Atoi(resultStr[i])
        result = append(result, num)
    }
    return bstFromPreorder(result)
}

func bstFromPreorder(preorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    root := &TreeNode{Val: preorder[0]}
    if len(preorder) == 1 {
        return root
    }
    var mid int
    for mid = 1; mid < len(preorder); mid++ {
        if preorder[mid] > preorder[0] {
            break
        }
    }
    root.Left = bstFromPreorder(preorder[1:mid])
    root.Right = bstFromPreorder(preorder[mid:])
    return root
}

func preorderTraversal(root *TreeNode) []int {
    result := []int{}
    if root == nil {
        return result
    }
    result = append(result, root.Val)
    result = append(result, preorderTraversal(root.Left)...)
    result = append(result, preorderTraversal(root.Right)...)
    return result
}


/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor()
 * deser := Constructor()
 * tree := ser.serialize(root)
 * ans := deser.deserialize(tree)
 * return ans
 */

# 297. Serialize and Deserialize Binary Tree

leetcode

Using marshal & unmarshal.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
    
}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if nil == root {
        return "[]"
    }
    b, _ := json.Marshal(root)
    return string(b)
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    if "[]" == data {
        return nil
    }
    var root TreeNode
    json.Unmarshal([]byte(data), &root)
    return &root
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */

# 652. Find Duplicate Subtrees

leetcode

Hash Map Of Serialized String

Time Complexity O(N^2)

Go through all the letters of that string. Each letter of this string is one node. Therefore, the first solution has a complexity of n ^ 2.

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
28
29
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []*TreeNode
var m map[string]int

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    res = []*TreeNode{}
    m = make(map[string]int)
    postorder(root)
    return res
}

func postorder(root *TreeNode) string {
    if root == nil {
        return "#"
    }
    serial := fmt.Sprintf("%d", root.Val) + "," + postorder(root.Left) + "," + postorder(root.Right)
    m[serial]++
    if m[serial] == 2 {
        res = append(res, root)
    }
    return serial
}

Cache the subtree structure

Time complexity decreased to O(N)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []*TreeNode
var serialToId map[string]int
var idToCount map[int]int
var id int

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    id = 1
    res = []*TreeNode{}
    serialToId = make(map[string]int)
    idToCount = make(map[int]int)
    postorder(root)
    return res
}

func postorder(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := postorder(root.Left)
    right := postorder(root.Right)
    serial := fmt.Sprintf("%v,%v,%v", left, root.Val, right)
    serialId, exists := serialToId[serial]
    if !exists {
        serialId = id
        serialToId[serial] = serialId
        id++
    }
    idToCount[serialId]++
    if idToCount[serialId] == 2 {
        res = append(res, root)
    }
    return serialId
}

# 606. Construct String from Binary Tree

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func tree2str(root *TreeNode) string {
    if root == nil {
        return ""
    }
    curVal := fmt.Sprintf("%v", root.Val)
    if root.Left == nil && root.Right == nil {
        return curVal
    }
    left := "(" + tree2str(root.Left) + ")"
    right := "(" + tree2str(root.Right) + ")"
    res := curVal + left
    if root.Right != nil {
        res += right
    }
    return res
}

# 124. Binary Tree Maximum Path Sum

leetcode

Here’s the situations:

  1. If there’s only 1 node, return it’s value.
  2. If there’s 2 nodes, return the sum of all non-negative nodes.
  3. If there’s 1 root with two child, the maximum path sum can be the left gain + right gain + root.Val. And the max gain can be root.Val + max(left gain, right gain)
  4. If the subtree’s gain is negative, there’s no need to consider it.
  5. The null is considered as 0 gain.
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
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var maxPath int
func maxPathSum(root *TreeNode) int {
    maxPath = math.MinInt32
    getMaxGain(root)
    return maxPath
}

func getMaxGain(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftGain := max(getMaxGain(node.Left), 0)
    rightGain := max(getMaxGain(node.Right), 0)
    
    curPath := node.Val + leftGain + rightGain
    maxPath = max(maxPath, curPath)
    
    return node.Val + max(leftGain, rightGain)
}
                    
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 129. Sum Root to Leaf Numbers

leetcode

Simple dfs problem.

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
28
29
30
31
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var sum int
func sumNumbers(root *TreeNode) int {
    if root == nil {
        return 0
    }
    sum = 0
    dfs(root, 0)
    return sum
}

func dfs(root *TreeNode, curNumber int) {
    if root == nil {
        return
    }
    curNumber *= 10
    curNumber += root.Val
    if root.Left == nil && root.Right == nil {
        sum += curNumber
        return
    }
    dfs(root.Left, curNumber)
    dfs(root.Right, curNumber)
}

# 988. Smallest String Starting From Leaf

leetcode

Go support lexicographical comparison using >, < operations.

Top-Down

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
28
29
30
31
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func smallestFromLeaf(root *TreeNode) string {
    return traverse(root, "")
}

func traverse(root *TreeNode, s string) string {
    if root == nil {
        return "|"
    }
    s = string(int('a') + root.Val) + s
    if root.Left == nil && root.Right == nil {
        return s
    }
    left := traverse(root.Left, s)
    right := traverse(root.Right, s)
    return min(left, right)
}

func min(a, b string) string {
    if a > b {
        return b
    }
    return a
}

# 230. Kth Smallest Element in a BST

leetcode

Use inorder 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
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var count int
var res int
var target int
func kthSmallest(root *TreeNode, k int) int {
    res = 0
    count = 0
    target = k
    traverse(root)
    return res
}

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    traverse(root.Left)
    if count == target {
        return
    }
    count++
    if count == target {
        res = root.Val
        return
    }
    traverse(root.Right)
}
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
28
29
func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    cnt := k
    if root != nil {
        stack = append(stack, root)
    }
    for len(stack) > 0 {
        node := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if node != nil {
            if node.Right != nil {
                stack = append(stack, node.Right)
            }
            if node.Left != nil {
                stack = append(stack, node.Left)
            }
            stack = append(stack, node)
            stack = append(stack, nil)
        } else {
            node = stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            if cnt == 0 {
                return node.Val
            }
            cnt--
        }
    }
    return -1
}

# 671. Second Minimum Node In a Binary Tree

leetcode

Divide and conquer

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func findSecondMinimumValue(root *TreeNode) int {
    if root == nil {
        return -1
    }
    if root.Left == nil && root.Right == nil {
        return -1
    }
    left := root.Left.Val
    right := root.Right.Val
    
    if root.Left.Val == root.Val {
        left = findSecondMinimumValue(root.Left)
    }
    if root.Right.Val == root.Val {
        right = findSecondMinimumValue(root.Right)
    }
    
    if left != -1 && right != -1 {
        return min(left, right)
    } else if left != -1 {
        return left
    } else {
        return right
    }
    return -1
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

Share 

 Previous post: System Design Next post: Code - DFS 

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo