题解 | #输出二叉树的右视图#

输出二叉树的右视图

http://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0

思路:上一题的从先序和中序重建二叉树可以直接拿来用,得到二叉树后层序遍历,输出每一层的最后一个元素即可。

package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
*/
func solve(xianxu []int, zhongxu []int) []int {
	// write code here
	var res []int
	node := reConstructBinaryTree(xianxu, zhongxu)
	levelOrderSlice := levelOrder(node)
	for i := 0; i < len(levelOrderSlice); i++ {
		res = append(res, levelOrderSlice[i][len(levelOrderSlice[i])-1])
	}
	return res
}
func reConstructBinaryTree(pre []int, vin []int) *TreeNode {
	// write code here
	if length := len(pre); length == 0 {
		return nil
	}
	i := 0
	for i = 0; i < len(vin); i++ {
		if vin[i] == pre[0] {
			break
		}
	}
	root := &TreeNode{pre[0], nil, nil}
	root.Left = reConstructBinaryTree(pre[1:i+1], vin[:i])
	root.Right = reConstructBinaryTree(pre[i+1:], vin[i+1:])
	return root
}
func levelOrder(root *TreeNode) [][]int {
	result := make([][]int, 0)
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, level int) {
		if node == nil {
			return
		}
		if level == len(result) {
			result = append(result, []int{})
		}
		result[level] = append(result[level], node.Val)
		dfs(node.Left, level+1)
		dfs(node.Right, level+1)
	}
	dfs(root, 0)
	return result
}

全部评论

相关推荐

小红书 后端选手 n*16*1.18+签字费期权
点赞 评论 收藏
分享
11-08 10:39
门头沟学院 C++
点赞 评论 收藏
分享
工作基本定了,比较满意。这深度学习真是难搞啊,论文看不懂,代码看不懂,不会改,创新点???&nbsp;还有一个月中期,怎么搞,已经抑郁了,没有小论文要求,我真是非常幸运了,不然就我这科研能力…………&nbsp;感觉自己对自己失去信心,无时无刻不在否定自己取得一些成绩都是运气好罢了,真的能顺利毕业吗?严重内耗、无力感爆棚啊…………
AI牛可乐:哎呀,听起来你最近压力好大呀,毕业论文和工作的双重压力一定让你感觉像是背了两座山呢。深度学习确实挺复杂的,就像是要在一片迷雾中找到出路一样。但是,你已经很棒了,工作都定好了,这是很大的成就呢! 论文的事情,别太担心。每个人都有看不懂代码和论文的时候,这是正常的。至于创新点嘛,有时候灵感就像小猫一样,需要一点一点地哄出来的。你可以先试试把你看过的资料整理一下,说不定就能找到新的思路呢。 中期答辩前,你可以列个计划,一步一步来,把大问题分解成小问题,一点一点克服。记得,你不是一个人在战斗,你的导师、同学都是你的战友哦。 至于信心嘛,别否定自己,每个人都会有低谷的时候。你已经取得的成绩,都是你实力的体现。毕业不是问题,只要你不放弃,就一定能顺利走过去的。加油哦,我相信你可以的! 对了,如果你愿意的话,可以点击我的头像,我们私信聊,也许我能帮你出出主意,或者就是简单地聊聊天,分散一下你的注意力也好呀。🐮💪🌟
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务