/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findDuplicateSubtrees(root *TreeNode) (result []*TreeNode) {
    m := make(map[string]int)
    
    dfs(root, m, &result)

    return result
}

func dfs(root *TreeNode, m map[string]int, result *[]*TreeNode) string {
    if root == nil {
        return ""
    }

    left := dfs(root.Left, m, result)
    right := dfs(root.Right, m, result)

    subtree := left + "," + right + "," + strconv.Itoa(root.Val)

    m[subtree]++

    if m[subtree] == 2 {
        *result = append(*result, root)
    }

    return subtree
}

/**
 * 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 "#"
    }

    return strconv.Itoa(root.Val) + ","  + this.serialize(root.Left) + "," + this.serialize(root.Right) 
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    var dfs func(nodes []string) (*TreeNode, int)
    dfs = func(nodes []string) (*TreeNode, int) {
        if len(nodes) == 0 {
            return nil, 0
        }

        firstNode := nodes[0]
        if firstNode == "#" {
            return nil, 1
        }

        left, leftLength := dfs(nodes[1:])
        right, rightLength := dfs(nodes[1+leftLength:])

        nodeVal, _ := strconv.Atoi(firstNode)
        node := &TreeNode{Val: nodeVal, Left: left, Right: right}

        return node, 1+leftLength+rightLength
    }

    nodes := strings.Split(data, ",")
    root, _ := dfs(nodes)

    return root
}



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

/**
 * 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 "#"
    }

    return this.serialize(root.Left) + "," + this.serialize(root.Right) + ","  + strconv.Itoa(root.Val) 
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    var dfs func(nodes []string) (*TreeNode, int)
    dfs = func(nodes []string) (*TreeNode, int) {
        if len(nodes) == 0 {
            return nil, 0
        }

        lastNode := nodes[len(nodes)-1]
        if lastNode == "#" {
            return nil, 1
        }

        right, rightLength := dfs(nodes[:len(nodes)-1])
        left, leftLength := dfs(nodes[:len(nodes)-1-rightLength])

        nodeVal, _ := strconv.Atoi(lastNode)
        node := &TreeNode{Val: nodeVal, Left: left, Right: right}

        return node, 1+leftLength+rightLength
    }

    nodes := strings.Split(data, ",")
    root, _ := dfs(nodes)

    return root
}



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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) int {
    return dfs(root)[k-1]
}

func dfs(root *TreeNode) (result []int) {
    if root == nil {
        return nil
    }

    result = dfs(root.Left)
    result = append(result, root.Val)
    result = append(result, dfs(root.Right)...)

    return result
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) (result int) {
    i := 0

    var traverse func (root *TreeNode)
    traverse = func (root *TreeNode) {
        if root == nil {
            return
        }
        
        traverse(root.Left)

        i++
        if i == k {
            result = root.Val
            return
        }

        traverse(root.Right)
    }

    traverse(root)

    return result
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    var dfs func (root *TreeNode, acc int) int
    dfs = func (root *TreeNode, acc int) int {
        if root == nil {
            return acc
        }

        newAcc := dfs(root.Right, acc)
        root.Val += newAcc
        return dfs(root.Left, root.Val)
    }

    dfs(root, 0)

    return root
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return validate(root, math.MinInt, math.MaxInt)
}

func validate(root *TreeNode, minValue, maxValue int) bool {
    if root == nil {
        return true
    }

    if root.Val <= minValue || root.Val >= maxValue {
        return false
    }

    return validate(root.Left, minValue, root.Val) && validate(root.Right, root.Val, maxValue)
}