LeetCode——二叉树的层序遍历（倒序）

LeetCode——二叉树的层序遍历（倒序）

题目描述： 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如： 给定二叉树 [3,9,20,null,null,15,7],

返回其自底向上的层次遍历为：

[ [15,7], [9,20], [3] ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路： 此题用层序遍历解决即可，我们定义一个总的需要返回的列表，然后定义一个队列，先让根节点入队列，开始遍历整棵树，我们在每层循环中定义一个小的列表，用来存储每一层节点的值，然后将列表第一个节点出列表，并且将它的值加入小列表，判断它的左右子树是否存在，若存在则加入队列，直到遍历完这层。在遍历完每一层，我们将存储每一层节点数值的小列表存储在总列表的第一个位置（因为题目要求倒序存放），当队列为空时则遍历完了所有节点，返回总列表即可。 这里提供Java和Python代码。

Java代码：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> levelOrder = new LinkedList<List<Integer>>(); if(root == null) return levelOrder; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while(!queue.isEmpty()){ List<Integer> level = new ArrayList<Integer>(); int size = queue.size(); while(size > 0){ TreeNode node = queue.poll(); level.add(node.val); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); size--; } levelOrder.add(0, level); } return levelOrder; } }

LeetCode测试结果：

Python代码：

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def levelOrderBottom(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ levelOrder = list() if root is None: return levelOrder queue = list() queue.append(root) while len(queue) != 0: level = list() size = len(queue) while size != 0: node = queue.pop(0) level.append(node.val) if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) size -= 1 levelOrder.insert(0, level) return levelOrder

LeetCode测试结果：