tree1.go

package LeetCode

import (
	"fmt"
)

func SSecondWalk(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Println(root.Val)
	SSecondWalk(root.Left)
	SSecondWalk(root.Right)
}

func SSecondWalk1(root *TreeNode) {
	var queue []*TreeNode
	queue = append(queue, root)
	for len(queue) != 0 {
		node := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		fmt.Println(node.Val)
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
}

func ThirdWalk(root *TreeNode) {
	var queue []*TreeNode
	for len(queue) != 0 || root != nil {
		for root != nil {
			queue = append(queue, root)
			root = root.Left
		}
		node := queue[len(queue)-1]
		queue = queue[:len(queue)-1]
		fmt.Println(node.Val)
		root = node.Right
	}

}

func LastWalk1(root *TreeNode) {
	var queue []*TreeNode
	var lastVisit *TreeNode
	for len(queue) != 0 || root != nil {
		queue = append(queue, root)
		root = root.Left
	}
	node := queue[len(queue)-1]
	if node.Right == nil || node == lastVisit {
		queue = queue[:len(queue)-1]
		fmt.Println(node.Val)
		lastVisit = node
	} else {
		root = root.Right
	}
}

func LevelOrder(root *TreeNode) [][]int {
	var queue []*TreeNode
	var res [][]int
	queue = append(queue, root)
	for len(queue) != 0 {
		var list []int
		l := len(queue)
		for i := 0; i < l; i++ {
			node := queue[i]
			list = append(list, node.Val)
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		res = append(res, list)
	}
	return res
}

// BFS 从0进队列，弹出之后计算上下左右的结果，将上下左右重新进队列进行二层操作
// 0 0 0 0
// 0 x 0 0
// x x x 0
// 0 x 0 0

// 0 0 0 0
// 0 1 0 0
// 1 x 1 0
// 0 1 0 0

// 0 0 0 0
// 0 1 0 0
// 1 2 1 0
// 0 1 0 0
func updateMatrix(matrix [][]int) [][]int {
	q := make([][]int, 0)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if matrix[i][j] == 0 {
				// 进队列
				point := []int{i, j}
				q = append(q, point)
			} else {
				matrix[i][j] = -1
			}
		}
	}
	directions := [][]int{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
	for len(q) != 0 {
		// 出队列
		point := q[0]
		q = q[1:]
		for _, v := range directions {
			x := point[0] + v[0]
			y := point[1] + v[1]
			if x >= 0 && x < len(matrix) && y >= 0 && y < len(matrix[0]) && matrix[x][y] == -1 {
				matrix[x][y] = matrix[point[0]][point[1]] + 1
				// 将当前的元素进队列，进行一次BFS
				q = append(q, []int{x, y})
			}
		}
	}
	return matrix

}