求树的左视图

求二叉树的左视图是什么意思呢? 就是一个二叉树, 在水平线上(从左往右)看到的第一个结点

还是有点抽象? 好吧, 上图直观点

这棵二叉树的左视图就是, 从左边看去, 第一个看到的结点, 就是当前二叉树所在层次的结点, 比如说:

• 第一层, 看到的是根节点, 那么第一层是 1
• 第二层, 看到的是左子树的根节点, 那么第一个层是 2, 由于有左子树了, 右子树的值已经被忽略了
• 第三层以此类推,

那么我们就要来分析这棵二叉树了

• 怎么样才能按层次输出这颗树呢?
• 怎么记录当前树所在的层次呢?

1. 首先一开始就想到了树的广度遍历, 使用队列作为辅助
2. 要记录树的层次, 就要把直到当遍历的结点所在的层次, 怎么做到的呢? 这个就需要用到额外的辅助空间了

基于以上两点, 我们定义出两个结构体:

1. 一个是用来定义二叉树结构的

type TreeNode struct {
	Left  *TreeNode
	Right *TreeNode
	Val   int
} // 定义一棵二叉树

2. 一个是用来定义当前遍历的结点所在的层数的

type Node struct {
	Node  *TreeNode // 这里是当前的结点的值
	Level int       // 这是当前的结点所在树的层次
}

最后就是按层次来遍历这棵二叉树了, 需要注意当前结点所在的层次

func LeftView(root *TreeNode) (ans [] int) {

	var nodes = make([]Node, 0)
	if root != nil {
		nodes = append(nodes, Node{Node: root, Level: 0}) // 如果根节点不是空的, 把更结点入队列, 同时将层次设置为 0
	}

	for len(nodes) != 0 {
		curr := nodes[0]
		nodes = nodes[1:]
		if len(ans) <= curr.Level {
			ans = append(ans, curr.Node.Val) // 将当前的第一个结点入队列
		}

		// 优先遍历左子树
		if curr.Node.Left != nil {
			nodes = append(nodes, Node{Node: curr.Node.Left, Level: curr.Level + 1})
		}
		// 然后再次遍历右子树
		if curr.Node.Right != nil {
			nodes = append(nodes, Node{Node: curr.Node.Right, Level: curr.Level + 1})
		}
	}
	return ans
}

完整的代码实现:

package main

import "fmt"

type TreeNode struct {
	Left  *TreeNode
	Right *TreeNode
	Val   int
} // 定义一棵二叉树

type Node struct {
	Node  *TreeNode // 这里是当前的结点的值
	Level int       // 这是当前的结点所在树的层次
}

func LeftView(root *TreeNode) (ans [] int) {

	var nodes = make([]Node, 0)
	if root != nil {
		nodes = append(nodes, Node{Node: root, Level: 0}) // 如果根节点不是空的, 把更结点入队列, 同时将层次设置为 0
	}

	for len(nodes) != 0 {
		curr := nodes[0]
		nodes = nodes[1:]
		if len(ans) <= curr.Level {
			ans = append(ans, curr.Node.Val) // 将当前的第一个结点入队列
		}

		// 优先遍历左子树
		if curr.Node.Left != nil {
			nodes = append(nodes, Node{Node: curr.Node.Left, Level: curr.Level + 1})
		}
		// 然后再次遍历右子树
		if curr.Node.Right != nil {
			nodes = append(nodes, Node{Node: curr.Node.Right, Level: curr.Level + 1})
		}
	}
	return ans
}

func main() {
	a := TreeNode{Val: 1}
	b := TreeNode{Val: 2}
	c := TreeNode{Val: 3}
	d := TreeNode{Val: 4}
	a.Left = &b
	a.Right = &c
	c.Right = &d

	// 当前这棵树的结构是
	/**
			1
	               / \
	              2   3
	                   \
                            4
	// output: 1,2,4

	*/
	ans := LeftView(&a)
	fmt.Println(ans) //: output [1 2 4]
}

可能遇到的错误的处理过程

途中我们可能只是遍历二叉树的左子树, 然而, 二叉树可能存在退化的现象, 或者说, 某些情况下, 二叉树的右子树才是而二叉树左视图的第一个结点

最后, 用递归遍历可以么? 怎么处理当前结点所在的层次的, 怎么填充返回的视图的