题目:
给定一棵二叉树,找到二叉树中最大距离的两个节点,返回最大距离
分析:
1利用二叉树的递归方法,要左子树和右子树要需要的信息
2 需要的信息为节点的高度和节点的最大上的最大距离
代码:
package main import ( "fmt" "math" ) type TreeNode struct { Data Data // 左子树指针 left *TreeNode // 右子树指针 right *TreeNode } type Data struct{ Name string Age int Score float32 } type Info struct{ Maxdistence int High int distence int } func process(x *TreeNode)Info{ if x==nil{ info:=Info{Maxdistence:0,High:0} return info } leftinfo:=process(x.left) rightinfo:=process(x.right) var info Info //当前节点左子树和右子树高度相加再加一,与下层返回给我的左大距离谁打我就记为当前的最大距离,另外保存我的最大距离 info.High=int(math.Max(float64(leftinfo.High),float64(rightinfo.High)))+1 // if info.High>int(math.Max(float64(leftinfo.High),float64(rightinfo.High))){ tmp:=int(math.Max(float64(leftinfo.Maxdistence),float64(rightinfo.Maxdistence))) // }else{ info.distence=leftinfo.High+rightinfo.High+1 info.Maxdistence=int(math.Max(float64(info.distence),float64(tmp))) // } return info } func main(){ // 根节点 var student Data student.Name = "root" student.Age = 10 student.Score = 90 var root TreeNode root.Data=student // 一级左子树 var student1l Data student1l.Name = "left1" student1l.Age = 20 student1l.Score = 80 var left1 TreeNode left1.Data=student1l root.left = &left1 // 一级右子树 var student1r Data student1r.Name = "right1" student1r.Age = 30 student1r.Score = 70 var right1 TreeNode right1.Data=student1r root.right = &right1 // 二级左子树 var left2 TreeNode var student2l Data student2l.Name = "left2" student2l.Age = 40 student2l.Score = 60 left2.Data=student2l left1.left = &left2 // 三级右子树 var left3 TreeNode var student3l Data student3l.Name = "left3" student3l.Age = 45 student3l.Score = 65 left3.Data=student3l left1.right = &left3 //四级右子树 var left4 TreeNode var student4l Data student4l.Name = "left4" student4l.Age = 46 student4l.Score = 66 left4.Data=student4l left3.right = &left4 //五级右子树 var left5 TreeNode var student5l Data student5l.Name = "left4" student5l.Age = 47 student5l.Score = 67 left5.Data=student5l left4.right = &left5 fmt.Println(process(&root)) }
总结:
1 节点的高度是经常会用到的需要子树反馈的主要信息,max(左子树的高度,右子树的高度)+自己这一层的高度1
2 节点的最大距离实际是两个子树的最大距离,和左右子树的高度的和再加上1,这三个值中最大的值