面试题-二叉树

lobo · · 657 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。 每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的null节点也计入长度)之间的长度。 示例 1: 输入: 1 / \ 3 2 / \ \ 5 3 9 输出: 4 解释: 最大值出现在树的第 3 层,宽度为 4 (5,3,null,9)。 示例 2: 输入: 1 / 3 / \ 5 3 输出: 2 解释: 最大值出现在树的第 3 层,宽度为 2 (5,3)。 示例 3: 输入: 1 / \ 3 2 / 5 输出: 2 解释: 最大值出现在树的第 2 层,宽度为 2 (3,2)。 示例 4: 输入: 1 / \ 3 2 / \ 5 9 / \ 6 7 输出: 8 解释: 最大值出现在树的第 4 层,宽度为 8 (6,null,null,null,null,null,null,7)。 注意: 答案在32位有符号整数的表示范围内。 func getHorizontalMaxNum(root *Node) int { var max int if nil == root { return max } nodeSlice := make([]*Node, 0) nodeSlice = append(nodeSlice, root) for { length := len(nodeSlice) if 0 == length { break } if max < length { max = length } tmpNodeSlice := make([]*Node, 0) for i := 0; i < length; i++ { tmpNode := nodeSlice[i] if tmpNode == nil { tmpNodeSlice = append(tmpNodeSlice, nil, nil) } else { tmpNodeSlice = append(tmpNodeSlice, tmpNode.Left, tmpNode.Right) } } i := 0 for { if i >= len(tmpNodeSlice) || nil != tmpNodeSlice[i] { break } i++ } tmpNodeSlice = tmpNodeSlice[i:] i = len(tmpNodeSlice) - 1 for { if i < 0 || nil != tmpNodeSlice[i] { break } i-- } tmpNodeSlice = tmpNodeSlice[:i+1] nodeSlice = tmpNodeSlice } return max }

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

657 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传