题目
给定一个二叉树的 根节点 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参数就可以