二叉树锯齿遍历

来源：go-interview / Algorithm

锯齿遍历（又称之为“之字形遍历”或“层次遍历”）是二叉树的一种遍历方式，其特点是每一层的节点在遍历时交替方向：奇数层从左到右，偶数层从右到左。以下是实现锯齿遍历的步骤和示例代码。

锯齿遍历步骤

1. 使用一个队列来辅助层次遍历。
2. 使用一个布尔值来标记当前层的遍历方向。
3. 按照层次遍历的顺序，依次将节点加入到结果列表中，根据当前层的遍历方向来决定顺序。

示例代码（Go）

package main
 
import (
	"fmt"
)
 
type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}
 
// 锯齿遍历函数
func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
 
	var result [][]int
	currentLevel := []*TreeNode{root}
	leftToRight := true
 
	for len(currentLevel) > 0 {
		var levelValues []int
		nextLevel := []*TreeNode{}
 
		for i := len(currentLevel) - 1; i >= 0; i-- {
			node := currentLevel[i]
			if leftToRight {
				levelValues = append(levelValues, node.Value)
			} else {
				levelValues = append([]int{node.Value}, levelValues...)
			}
			if node.Left != nil {
				nextLevel = append(nextLevel, node.Left)
			}
			if node.Right != nil {
				nextLevel = append(nextLevel, node.Right)
			}
		}
 
		result = append(result, levelValues)
		currentLevel = nextLevel
		leftToRight = !leftToRight // 切换方向
	}
 
	return result
}
 
func main() {
	// 构建二叉树
	root := &TreeNode{Value: 1}
	root.Left = &TreeNode{Value: 2}
	root.Right = &TreeNode{Value: 3}
	root.Left.Left = &TreeNode{Value: 4}
	root.Left.Right = &TreeNode{Value: 5}
	root.Right.Left = &TreeNode{Value: 6}
	root.Right.Right = &TreeNode{Value: 7}
 
	// 执行锯齿遍历
	result := zigzagLevelOrder(root)
	for _, level := range result {
		fmt.Println(level)
	}
}

输出结果

对于以下树结构：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

锯齿遍历的输出将会是：

[1]
[3 2]
[4 5 6 7]

总结

锯齿遍历通过交替的层次访问顺序，展现了树的节点，适用于需要层次和方向的遍历场景。如果有更多问题或需要进一步的示例，请告诉我！