671. 二叉树中第二小的节点

671. 二叉树中第二小的节点

//递归，对root，左右子树作为整体分析，时空都是On
func findSecondMinimumValue(root *TreeNode) int {
    return dfs(root , root.Val)
}
func dfs(root *TreeNode, val int) int {
    if root == nil {
        return -1       // -1 代表分支找到叶节点，此条路径无更大节点
    }
    if root.Val > val {
        return root.Val     //递归结束条件 当发现第一个大的节点，立刻返回
    }
    node_Left := dfs(root.Left, val)
    node_Right := dfs(root.Right, val)
    if node_Left == -1 {    // -1 左子树无更大节点，对右子树递归
        return node_Right
    }
    if node_Right == -1 {
        return node_Left
    }
    return min(node_Left,node_Right)    //两边都找到，返回左右子树中的最小节点
}
func min(a,b int) int {
    if a > b {
        return b
    }
    return a
}

//迭代
func findSecondMinimumValue(root *TreeNode) int {
    if root == nil {
        return -1
    }

    res, queue, min := -1, []*TreeNode{root}, root.Val
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Val > min {

            // 遇到第一个符合条件的节点 直接赋值，否则 与结果比较 取较小的值作为新的结果
            if res == -1 {
                res = node.Val
            } else {
                res = minRes(res, node.Val)
            }

            // 如果当前节点的Val大于了根节点的值 那么以当前节点为根节点的值都不用判断 跳过即可
            continue
        }

        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }

    }
    return res
}

func minRes(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}