leetcode199 二叉树的右视图

题目

给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例

在这里插入图片描述
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

解析

这道题首先能想到的办法,就是使用迭代法层次遍历,然后在每一层的最右边那个节点加入到结果集中即可

func rightSideView(root *TreeNode) []int {
	ans := []int{}
	if root == nil {
		return ans
	}
	queue := list.New()
	queue.PushBack(root)
	for queue.Len() > 0 {
		length := queue.Len()
		for i := 0; i < length; i++ {
			node := queue.Remove(queue.Front()).(*TreeNode)
			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
			if i == length-1 {
				ans = append(ans, node.Val)
			}
		}
	}
	return ans
}

还有一种更为巧妙的方法是,使用递归法,先递归右子树,再递归左子树,同时在递归的时候在多传一个参数是二叉树的深度,当深度等于答案结果集的长度时,就将此时递归到的节点追加到答案中

func xxx(root *TreeNode) []int {
	ans := []int{}
	var traversal func(node *TreeNode, depth int)

	traversal = func(node *TreeNode, depth int) {
		if node == nil {
			return
		}
		if depth == len(ans) {
			ans = append(ans, node.Val)
		}
		fmt.Print(node.Val)
		traversal(node.Right, depth+1)
		traversal(node.Left, depth+1)
	}
	traversal(root, 0)
	return ans
}

上面的代码再解释下,因为递归先遍历的时右子树,在根节点的时候,深度为0,结果集的长度也为0,所以把根节点的值加入结果集;然后先递归右子树,深度为1,结果集的长度也为1,就也加进去,依此类推。
每次优先遍历右节点而非左节点,实际上保证了“某一层第一次被访问的节点一定在这一层的最右边”,因此只需要能够判断某一层是不是被第一次访问就行,怎么判断?加一个depth参数就可以

上一篇:区块链安全-----接口测试-Postman


下一篇:线程安全---synchronized-程序竟然正常运行了,那么这个synchronized到底有什么魔力呢