783. 二叉搜索树节点最小距离

原创
2020/04/25 15:29
阅读数 22


783. 二叉搜索树节点最小距离


image.png

783.二叉搜索树节点最小距弃

难度简单

55

给定一个二叉搜索树的根节点oot,返回树中任意两节点的差的最小值.

示例:

输入:root[4,2,6,uuu

输出:1

解释:

注意,root是树节点对象(Treenodeobject),而不是数组.

给定的树[4,2,6,1,3,ul,uu表示为下图:

package main

import (
    "fmt"
    "strconv"
    "strings"
)

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
 }
 // 中序遍历
func minDiffInBST(root *TreeNode) int {
    var res []int
    stack := make([]*TreeNode,0)
    for root!=nil||len(stack)>0{
        for root!=nil{
            stack = append(stack,root)
            root =root.Left
        }
        node :=stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res,node.Val)
        root = node.Right
    }
    if len(res)<2 {
        return res[0]
    }
    min :=res[1]-res[0]
    for i:=2;i<len(res);i++{
        r := res[i]-res[i-1]
        if min>r{
            min = r
        }
    }
    return min
}

func BuildBinaryTree(src string)*TreeNode{
    src =src[1:len(src)-1]
    strList := strings.Split(src, ",")
    var currNode *TreeNode
    var root *TreeNode
    var queue []*TreeNode
    for i :=0;i<len(strList);i+=2{
        if i==0 {
            v,_:=strconv.Atoi(strList[i])
            currNode =&TreeNode{Val:v}
            root =currNode
            queue = append(queue,currNode)
        }
        if len(queue)>0 {
            currNode =queue[0]
            queue =queue[1:]
        }else {
            break
        }
        if i+1<len(strList)&&strList[i+1]!="null"{
            v,_:=strconv.Atoi(strList[i+1])
            currNode.Left = &TreeNode{Val:v}
            queue = append(queue,currNode.Left)
        }
        if i+2<len(strList)&&strList[i+2]!="null"{
            v,_:=strconv.Atoi(strList[i+2])
            currNode.Right = &TreeNode{Val:v}
            queue = append(queue,currNode.Right)
        }
    }
    return root
}

func main() {
    root := BuildBinaryTree("[4,2,6,1,3,null,null]")
    fmt.Println(minDiffInBST(root))
    root1 :=BuildBinaryTree("[27,null,34,null,58,50,null,44,null,null,null]")
    fmt.Println(minDiffInBST(root1))
}


image.png

显示详情>

通过

执行结果:

执行用时:0ms,在所有GO提交中击败了100.00%的用户

内存消耗:2.4MB,在所有GO提交中击败了100.00%的用户

炫耀一下:

本文同步分享在 博客“羊羽”(other)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享

作者的其它热门文章

加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部