题目描述
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
示例:
例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的层次遍历为: [ [15,7], [9,20], [3] ]
思路
1.思路与102. 二叉树的层次遍历大致相同,只要需要将每一层的数据插入到结果集的时候改为头插法。
Java代码实现
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); LinkedList<TreeNode> nodes = new LinkedList<>(); List<Integer> curVals = new ArrayList<>(); int curMax = 1; int count = 0; if(root != null) nodes.add(root); while(!nodes.isEmpty()){ TreeNode cur = nodes.pollFirst(); curVals.add(cur.val); count++; if(cur.left != null) nodes.add(cur.left); if(cur.right != null) nodes.add(cur.right); //进行一系列的初始化操作 if(count == curMax){ curMax = nodes.size(); count = 0; //头插法 res.add(0,curVals); curVals = new ArrayList<>(); } } return res; }