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

输出二叉树的右视图

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


/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
*/
//BFS(只输出最右边的节点)
func solve(preorder []int, inorder []int) []int {
	root := buildTree(preorder, inorder)
	if root == nil {
		return []int{}
	}

	queue := []*TreeNode{root}
	levels := []int{}

	for len(queue) > 0 {
		n := len(queue)

		for i := 0; i < n; i++ {
			root = queue[0]
			queue = queue[1:]

			if root.Left != nil {
				queue = append(queue, root.Left)
			}
			if root.Right != nil {
				queue = append(queue, root.Right)
			}

			if i == n-1 {
				levels = append(levels, root.Val)
			}
		}
	}
	return levels
}
//构造二叉树
func buildTree(preorder, inorder []int) *TreeNode {
	return build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}
func build(preorder []int, preStart, preEnd int, inorder []int, inStart, inEnd int) *TreeNode {
	if preStart > preEnd {
		return nil
	}
	rootVal := preorder[preStart]
	index := 0
	for i := inStart; i <= inEnd; i++ {
		if rootVal == inorder[i] {
			index = i
			break
		}
	}
	root := &TreeNode{Val: rootVal}
	leftSize := index - inStart
	root.Left = build(preorder, preStart+1, preStart+leftSize, inorder, inStart, index-1)
	root.Right = build(preorder, preStart+leftSize+1, preEnd, inorder, index+1, inEnd)
	return root
}
全部评论

相关推荐

Rena1ssanc...:对的,要是面评没太烂,勤更新简历等捞就行了,腾讯可以无限复活
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:35
虽然不怎么光彩,经过这件事,可能我真的要去认同“面试八股文早该淘汰!不会用AI作弊的程序员=新时代文盲!”这句话了
HellowordX:Ai的出现是解放劳动力的,不是用来破坏公平竞争环境的,这样下去,轻则取消所有线上面试,严重了会影响整个行业对所有人产生影响,企业会拉高入职考核各种离谱考核会层出不穷
你找工作的时候用AI吗?
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务