算法题/树的BFS：zigzag遍历

题目

给定一棵二叉树，填充一个数组，以逆序表示其逐级遍历，即从最底层（叶子结点所在层）开始遍历，而不是从最高层（根节点所在层）开始遍历。我们应该在单独的子数组中从左到右填充每个级别中所有节点的值。

解答

Java

import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;

      TreeNode(int x) {
        val = x;
      }
};

class ReverseLevelOrderTraversal {
        public static List<List<Integer>> traverse(TreeNode root) {
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            if (root == null)
                return result;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int levelSize = queue.size();
                List<Integer> currentLevel = new ArrayList<>(levelSize);
                for (int i = 0; i < levelSize; i++) {
                    TreeNode currentNode = queue.poll();
                    //添加遍历到的元素的值到currentLevel中
                    currentLevel.add(currentNode.val);
                    //添加当前层的子节点到队列中
                    if (currentNode.left != null)
                        queue.offer(currentNode.left);
                    if (currentNode.right != null)
                        queue.offer(currentNode.right);
                }
                //每次在结果列表的开头添加当前层的元素，而不是末尾
                result.add(0, currentLevel);
            }
            return result;
        }

        public static void main(String[] args) {
            TreeNode root = new TreeNode(12);
            root.left = new TreeNode(7);
            root.right = new TreeNode(1);
            root.left.left = new TreeNode(9);
            root.right.left = new TreeNode(10);
            root.right.right = new TreeNode(5);
            List<List<Integer>> result = ReverseLevelOrderTraversal.traverse(root);
            System.out.println("Reverse level order traversal: " + result);
        }
}

JavaScript

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class ReverseLevelOrderTraversal {
  static traverse(root) {
    const result = [];
    if (root === null) {
      return result;
    }
    const queue = [];
    queue.push(root);
    while (queue.length > 0) {
      const levelSize = queue.length;
      const currentLevel = [];
      for (let i = 0; i < levelSize; i++) {
        const currentNode = queue.shift();
        currentLevel.push(currentNode.val);
        if (currentNode.left !== null) {
          queue.push(currentNode.left);
        }
        if (currentNode.right !== null) {
          queue.push(currentNode.right);
        }
      }
      result.unshift(currentLevel);
    }
    return result;
  }
}

const root = new TreeNode(12);
root.left = new TreeNode(7);
root.right = new TreeNode(1);
root.left.left = new TreeNode(9);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(5);

const result = ReverseLevelOrderTraversal.traverse(root);
console.log("Reverse level order traversal: ", result);

Python

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class ReverseLevelOrderTraversal:
    @staticmethod
    def traverse(root):
        result = []
        if root is None:
            return result
        queue = deque()
        queue.append(root)
        while queue:
            level_size = len(queue)
            current_level = []
            for _ in range(level_size):
                current_node = queue.popleft()
                current_level.append(current_node.val)
                if current_node.left:
                    queue.append(current_node.left)
                if current_node.right:
                    queue.append(current_node.right)
            result.insert(0, current_level)
        return result

root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(9)
root.right.left = TreeNode(10)
root.right.right = TreeNode(5)

result = ReverseLevelOrderTraversal.traverse(root)
print("Reverse level order traversal:", result)

Go

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type ReverseLevelOrderTraversal struct{}

func (ReverseLevelOrderTraversal) traverse(root *TreeNode) [][]int {
	result := [][]int{}
	if root == nil {
		return result
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		levelSize := len(queue)
		currentLevel := make([]int, levelSize)
		for i := 0; i < levelSize; i++ {
			currentNode := queue[0]
			queue = queue[1:]
			currentLevel[i] = currentNode.Val
			if currentNode.Left != nil {
				queue = append(queue, currentNode.Left)
			}
			if currentNode.Right != nil {
				queue = append(queue, currentNode.Right)
			}
		}
		result = append([][]int{currentLevel}, result...)
	}
	return result
}

func main() {
	root := &TreeNode{Val: 12}
	root.Left = &TreeNode{Val: 7}
	root.Right = &TreeNode{Val: 1}
	root.Left.Left = &TreeNode{Val: 9}
	root.Right.Left = &TreeNode{Val: 10}
	root.Right.Right = &TreeNode{Val: 5}

	r := ReverseLevelOrderTraversal{}
	result := r.traverse(root)
	fmt.Println("Reverse level order traversal:", result)
}