title: 算法小练——二叉树的层次遍历II
categories:

• Algorithms
  tags:
• easy
  abbrlink: 752527107
  date: 2019-11-24 19:59:03

二叉树的层次遍历 II

描述

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

示例

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

    3 
    / \
  9  20
       /  \
     15   7
返回其自底向上的层次遍历为：

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

代码

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
   List<List<Integer>> lists1 = new ArrayList<>();
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		if(root==null){
			return lists1;
		}
		helper2(root,0,lists1);
		return lists1;
	}
	public void helper2(TreeNode treeNode,int level,List<List<Integer>> lists) {
		if(lists1.size()==level){
			lists1.add(0,new ArrayList<>());
		}
		lists1.get(lists.size()-1-level).add(treeNode.val);
		if(treeNode.left!=null){
			helper2(treeNode.left,level+1,lists1);
		}
		if(treeNode.right!=null){
			helper2(treeNode.right,level+1,lists1);
		}
	}
}

笔记

二叉树的层次遍历

参考这个，总的来说还是BFS，只是存的时候反着存。