算法题/树的BFS：翻转层序遍历

题目

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

解答

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(x) {
    this.val = x;
    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中
        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;
  }

  static main() {
    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);
  }
}

ReverseLevelOrderTraversal.main();

Python

from collections import deque

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

class ReverseLevelOrderTraversal:
    def traverse(root):
        result = []
        if not root:
            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中
                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

    def main():
        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)

ReverseLevelOrderTraversal.main()

Go

package main

import (
	"container/list"
	"fmt"
)

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

func traverse(root *TreeNode) [][]int {
	result := [][]int{}
	if root == nil {
		return result
	}

	queue := list.New()
	queue.PushBack(root)
	for queue.Len() > 0 {
		levelSize := queue.Len()
		currentLevel := make([]int, levelSize)
		for i := 0; i < levelSize; i++ {
			currentNode := queue.Remove(queue.Front()).(*TreeNode)
			// 添加遍历到的元素的值到currentLevel中
			currentLevel[i] = currentNode.Val
			// 添加当前层的子节点到队列中
			if currentNode.Left != nil {
				queue.PushBack(currentNode.Left)
			}
			if currentNode.Right != nil {
				queue.PushBack(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}
	result := traverse(root)
	fmt.Println("Reverse level order traversal:", result)
}