论述题1. 题目描述:
从树的根结点开始往下访问一直到叶子结点经过的所有结点形成一条路径。找出所有的这些路径,使其满足这条路径上所有结点数据的和等于给定的整数。例如:给定如下二叉树与整数8,满足条件的路径为6->3->-1(6+3-1=8)。
可以通过对二叉树的遍历找出所有的路径,然后判断各条路径上所有结点的值的和是否与给定的整数相等,如果相等,则打印出这条路径。具体实现方法可以通过对二叉树进行先序遍历来实现,实现思路为:对二叉树进行先序遍历,把遍历的路径记录下来,当遍历到叶子结点时,判断当前的路径上所有结点数据的和是否等于给定的整数,如果相等则输出路径信息,示例代码如下:
package main
import (
."github.com/isdamir/gotype"
"fmt"
)
//方法功能:打印出满足所有结点数据的和等于num的所有路径
//参数:root:二叉树根结点;num:给定的整数;sum:当前路径上所有结点的和
//v:用业存储从根结点到当前遍历到结点的路径
func FindRoad(root *BNode, num, sum int, v []int){
//记录当前遍历的root结点
sum+=root.Data.(int)
v=append(v, root.Data.(int))
//当前结点是叶子结点且遍历的路径上所有结点的和等于num
if root.LeftChild==nil&&root.RightChild==nil&&sum==num{
for_, v:=range v {
fmt.Print(v, " ")
}
fmt.Println()
}
//遍历root的左子树
if root.LeftChild!=nil {
FindRoad(root.LeftChild, num, sum, v)
}
//遍历root的右子树
if root.RightChild!=nil {
FindRoad(root.RightChild, num, sum, v)
}
//清除遍历的路径
sum-=v[len(v)-1]
v=v[:len(v)-1]
}
func createTree()*BNode {
root:=NewBNode()
node1:=NewBNode()
node2:=NewBNode()
node3:=NewBNode()
node4:=NewBNode()
root.Data=6
node1.Data=3
node2.Data=-7
node3.Data=-1
node4.Data=9
root.LeftChild=node1
root.RightChild=node2
node1.LeftChild=node3
node1.RightChild=node4
return root
}
func main(){
root:=createTree()
fmt.Print("满足路径结点和等于8的路径为:")
FindRoad(root, 8, 0, make([]int, 0))
}
程序的运行结果为
满足路径结点和等于8的路径为:6 3 -1
算法性能分析:
这种方法与二叉树的先序遍历有着相同的时间复杂度O(n),此外,这种方法用一个数组存放遍历路径上结点的值,在最坏的情况下时间复杂度为O(n)(所有结点只有左子树,或所有结点只有右子树),因此,空间复杂度为O(n)。
[考点] 如何在二叉树中找出与输入整数相等的所有路径
2. 题目描述:
二叉树的镜像就是二叉树对称的二叉树,就是交换每一个非叶子结点的左子树指针和右子树指针,如下图所示,请写出能实现该功能的代码。注意:请勿对该树做任何假设,它不一定是平衡树,也不一定有序。
从上图可以看出,要实现二叉树的镜像反转,只需交换二叉树中所有结点的左右孩子即可。由于对所有的结点都做了同样的操作,因此,可以用递归的方法来实现,实现代码如下(由于需要调用printTreeLayer层序打印二叉树,这种方法中使用了队列来实现):
package main
import(
."github.com/isdamir/gotype"
"fmt"
)
//对二叉树进行镜像反转
func ReverseTree(root*BNode){
if root==nil{
return
}
ReverseTree(root.LeftChild)
ReverseTree(root.RightChild)
tmp:=root.LeftChild
root.LeftChild=root.RightChild
root.RightChild=tmp
}
func main(){
data:=[]int{1, 2, 3, 4, 5, 6, 7}
fmt.Println("数组:", data)
root=ArrayToTree(data, 0, len(data)-1)
tint.Print("二叉树层序遍历结果为:")
PrintTreeLayer(root)
fmt.Println()
ReverseTree(root)
fmt.Print("反转后的二叉树层序遍历结果为:")
PrintTreeLayer(root)
}
程序的运行结果为
二叉树层序遍历结果为:4 2 6 1 3 5 7
反转后的二叉树层序遍历结果为:4 6 2 7 5 3 1
算法性能分析:
由于对给定的二叉树进行了一次遍历,因此,时间复杂度为O(n)。
[考点] 如何对二叉树进行镜像反转
3. 题目描述:
对于一棵二叉排序树,令f=(最大值+最小值)/2,设计一个算法,找出距离f值最近且大于f值的结点。例如,下图所给定的二叉排序树中,最大值为7,最小值为1,因此,f=(1+7)/2=4,那么在这棵二叉树中,距离结点4最近并且大于4的结点为5。
首先需要找出二叉排序树中的最大值与最小值。由于二叉排序树的特点是:对于任意一个结点,它的左子树上所有结点的值都小于这个结点的值,它的右子树上所有结点的值都大于这个结点的值。因此,在二叉排序树中,最小值一定是最左下的结点,最大值一定是最右下的结点。根据最大值与最小值很容易就可以求出f的值。接下来对二叉树进行中序遍历。如果当前结点的值小于f,那么在这个结点的右子树中接着遍历,否则遍历这个结点的左子树。实现代码如下。
package main
import(
."github.com/isdamir/gotype"
"fmt"
)
//方法功能:查找值最小的结点
//输入参数:root:根结点
//返回值:值最小的结点
func getMinNode(node*BNode)*BNode{
if node==nil{
return node
}
tmp:=node
for tmp.LeftChild!-nil{
tmp=tmp.LeftChild
}
return tmp
}
//方法功能:查找值最大的结点
//输入参数:root:根结点
//返回值:值最大的结点
func getMaxNode(node*BNode)*BNode{
if node==nil{
return node
}
tmp:=node
for tmp.RightChild!=nil{
tmp=tmp.RightChild
}
return tmp
}
func getNode(root*BNode)*BNode {
maxNode:=getMaxNode(root)
minNode:=getMinNode(root)
mid:=(maxNode.Data.(int)+minNode.Data.(int))/2
var result*BNode
for root!=nil{
//当前结点的值不大于f,则在右子树上找
if(root.Data.(int)<=mid){
root=root.RightChild
}else{
//否则在左子树上找
result=root
root=root.LeftChild
}
}
return result
}
func main(){
data:=[]int{1, 2, 3, 4, 5, 6, 7}
fmt.Println("数组:", data)
root:=ArrayToTree(data, 0, len(data)-1)
fmt.Println(getNode(root).Data)
}
程序的运行结果为
5
算法性能分析:
这种方法在查找最大结点与最小结点时的时间复杂度为O(h),h为二叉树的高度,对于有N个结点的二叉排序树,最大的高度为O(n),最小的高度为O(logn)。同理,在查找满足条件的结点的时候,时间复杂度也是O(h)。综上所述,这种方法的时间复杂度在最好的情况下是O(logn),最坏的情况下为O(n)。
[考点] 如何在二叉排序树中找出第一个大于中间值的结点
4. 题目描述:
给定一棵二叉树,求各个路径的最大和,路径可以以任意结点作为起点和终点。比如给定以下二叉树:
各路径的和为左叶子结点到当前结点到右叶子结点,即5+2+3=10。
本题可以通过对二叉树进行后序遍历来解决,具体思路如下:
对于当前遍历到的结点root,假设已经求出在遍历root结点前最大的路径和为max:
(1)求出以root.left为起始结点,叶子结点为终结点的最大路径和为maxLeft。
(2)同理求出以root.right为起始结点,叶子结点为终结点的最大路径和maxRight。
包含root结点的最长路径可能包含如下三种情况:
(1)leftMax=root.val+maxLeft(右子树最大路径和可能为负)。
(2)rightMax=root.val+maxRight(左子树最大路径和可能为负)。
(3)allMax=root.val+maxLeft+maxRight(左右子树的最大路径和都不为负)。
因此,包含root结点的最大路径和为tmpMax=max(leftMax,rightMax,allMax)。
在求出包含root结点的最大路径后,如果tmpMax>max,那么更新最大路径和为tmpMax。
实现代码如下:
package main
import(
"math"
."github.com/isdamir/gotype"
"fmt"
)
typeIntRefstruct{
Val int
}
//求a,b,c的最大值
func Max(a, b, c int)int{
varmaxint
if a>b{
max=a
}else{
max=b
}
if max<c{
max=c
}
return max
}
//寻找最长路径
func FindMaxPathRecursive(root *BNode, max *IntRef)int {
if root==nil {
return0
}
//求左子树以root.left为起始结点的最大路径和
sumLeft:= FindMaxPathRecursive(root.LeftChild, max)
//求右子树以root.right为起始结点的最大路径和
sumRight:= FindMaxPathRecursive(root.RightChild, max)
//求以root为起始结点,叶子结点为结束结点的最大路径和
allMax:= root.Data.(int)+sumLeft+sumRight
leftMax:= root.Data.(int) + sumLeft
rightMax:= root.Data.(int) + sumRight
tmpMax:= Max(allMax, leftMax, rightMax)
if tmpMax>max.Val {
max.Val = tmpMax
}
var subMaxint
if sumLeft > sumRight {
subMax=sumLeft
}else{
subMax=sumRight
}
//返回以root为起始结点,叶子结点为结束结点的最大路径和
return root.Data.(int) + subMax
}
func FindMaxPath(root *BNode)int {
max:=&IntRef{Val:math.MinInt64 }
FindMaxPathRecursive(root, max)
return max.Val
}
func main() {
data:=[]int {2, 3, 5}
fmt.Println("数组:", data)
root:=ArrayToTree(data, 0, len(data)-1)
fmt.Println(FindMaxPath(root))
}
程序的运行结果为
10
算法性能分析:
二叉树后序遍历的时间复杂度为O(n),因此,这种方法的时间复杂度也为O(n)。
[考点] 如何在二叉树中找出路径最大的和
5. 题目描述:
反向DNS查找指的是使用Internet IP地址查找域名。例如,如果你在浏览器中输入74.125.200.106,它会自动重定向到对应网址。
如何实现反向DNS查找缓存?
要想实现反向DNS查找缓存,主要需要完成如下功能:
(1)将IP地址添加到缓存中的URL映射。
(2)根据给定IP地址查找对应的URL。
对于本题的这种问题,常见的一种解决方案是使用哈希法(使用map来存储IP地址与URL之间的映射关系),由于这种方法相对比较简单,这里就不做详细介绍了。下面重点介绍另外一种方法:Trie树。这种方法的主要优点如下:
(1)使用Trie树,在最坏的情况下的时间复杂度为O(i),而哈希方法在平均情况下的时间复杂度为O(1)。
(2)Trie树可以实现前缀搜索(对于有相同前缀的IP地址,可以寻找所有的URL)。
当然,由于树这种数据结构本身的特性,所以使用树结构的一个最大的缺点就是需要耗费更多的内存,但是对于本题而言,这却不是一个问题,因为Internet IP地址只包含有11个字母(0到9和.)。所以,本题实现的主要思路为:在Trie树中存储IP地址,而在最后一个结点中存储对应的域名。实现代码如下:
package main
import(
."github.com/isdamir/gotype"
"fmt"
)
var CharCount=11
typeDNSCachhestruct{
root*TrieNode
}
func(p*DNSCache)getIndexFromRune(char rune)int{
if char=='.'{
return 10
}else{
returnint(char)-'0'
}
}
func(p*DNscache)getRuneFromIndex(i int)rune{
if i==10{
return '.'
}else{
returnrune('0'+i)
}
}
//把一个IP地址和相应的URL添加到Trie树中,最后一个结点是URL
func (p*DNSCache) Insert(ip, url string){
pCrawl:=p.root
for_, v:= range []rune(ip) {
//根据当前遍历到的IP中的字符,找出子结点的索引
index:=p.getlndexFromRune(v)
//如果子结点不存在,则创建一个
if pCrawl.Child[index] ==nil {
pCrawl.Child[index]=NewTrieNode(CharCount
}
//移动到子结点
pCrawl=pCrawl.Child[index]
}
//在叶子结点中存储IP地址对应的URL
pCrawl.IsLeaf=true
pCrawl.Url=url
}
//通过IP地址找到对应的URL
func (p *DNSCache) SearchDNSCache(ip string)string{
pCrawl:=p.root
for_, v:=range []rune(ip){
index:=p.getIndexFromRune(v)
if pCrawl.Child[index]==nil {
return""
}
pCrawl=pCrawl.Child[index]
}
//返回找到的URL
if pCrawl!=nil&&pCrawl.IsLeaf{
return pCrawl.Url
}
return""
}
func NewDNSCache()*DNSCache{
return&DNSCache {root:NewTrieNode(CharCount)}
}
func main() {
ipAdds:=[]string{"10.57.11.127", "121.57.61.129", "66.125.100.103"}
urls:=[]string{"www.s}amsung.com", "www.samsung.net"
dnsCache:=NewDNSCache()
//把IP地址和对应的URL插入到Trie树中
fori, v:=range ipAdds{
dnsCache.Insert(v, urls[i])
}
ip:=ipAdds[1]
result:=dnsCache.SearchDNSCache(ip)
if result!=""{
fmt.Println("找到了IP对应的URL:\n", ip, "--->", result)
}else{
fmt.Println("没有找到对应的URL")
}
}
程序的运行结果为
找到了IP对应的URL:
121.57.61.129-->www.samsung.net
显然,由于上述算法中涉及的IP地址只包含特定的11个字符(数字和.),所以,该算法也有一些异常情况未处理,例如不能处理用户输入的不合理的IP地址的情况,有兴趣的读者可以继续朝着这个思路完善后面的算法。
[考点] 如何实现反向DNS查找缓存