【LeetCode】二叉树算法题的几种解法与思路
【LeetCode】二叉树算法题的几种解法与思路
题目名称
二叉树的层次遍历 II
题目地址
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
题目描述
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如： 给定二叉树 [3,9,20,null,null,15,7],
示例 1:
输入: [3,9,20,null,null,15,7]
输出: [[15,7],[9,20],[3]] 示例 2:
输入: [3,9,20,1,2,15,7]
输出: [[1,2,15,7],[9,20],[3]] 解题源码
另外还有方式，使用队列是没问题的，在这里使用递归方式进行
方法一
源码
public class Topic107_1 {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode left = new TreeNode(9);
TreeNode right = new TreeNode(20);
root.left = left;
root.right = right;
TreeNode left1 = new TreeNode(15);
TreeNode right1 = new TreeNode(7);
right.left = left1;
right.right = right1;
TreeNode left2 = new TreeNode(2);
TreeNode right2 = new TreeNode(3);
left.left = left2;
left.right = right2;
List<List<Integer>> n = levelOrderBottom(root);
System.out.println(n);
}
public static List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> node = new ArrayList<>();
List<Integer> n = new ArrayList<>();
Map<Integer,List<Integer>> layer = new HashMap<>();
layer.put(0,n);
addNode(root, n,layer,1);
for (Integer integer : layer.keySet()) {
List<Integer> c = layer.get(integer);
if(c.size()>0) {
node.add(c);
}
}
//倒叙输出
Collections.reverse(node);
return node;
}
/**
* 先递归，再倒叙输出
* 重点就是层级，利用Map的key存储层级
* @param root
* @param n
* @param layer
* @param level
*/
private static void addNode(TreeNode root, List<Integer> n,Map<Integer,List<Integer>> layer,Integer level) {
if(root==null){
return;
}
TreeNode left = root.left;
TreeNode right = root.right;
n.add(root.val);
List<Integer> next = new ArrayList<>();
if(layer.containsKey(level)){
next = layer.get(level);
}else {
layer.put(level,next);
}
if(left!=null){
addNode(left,next,layer,level+1);
}
if(right!=null){
addNode(right,next,layer,level+1);
}
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}消耗
- 执行用时 : 2 ms
- 内存消耗 : 36.5 MB
方法二
较于方法一，不使用Map，直接使用List记录下层级
源码
public class Topic107_2 {
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode left = new TreeNode(9);
TreeNode right = new TreeNode(20);
root.left = left;
root.right = right;
TreeNode left1 = new TreeNode(15);
TreeNode right1 = new TreeNode(7);
right.left = left1;
right.right = right1;
TreeNode left2 = new TreeNode(2);
TreeNode right2 = new TreeNode(3);
left.left = left2;
left.right = right2;
List<List<Integer>> n = levelOrderBottom(root);
System.out.println(n);
}
public static List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> node = new ArrayList<>();
if(root==null){
return node;
}
addNode(root,node,0);
//倒叙输出
Collections.reverse(node);
return node;
}
/**
* 先递归，再倒叙输出
* 重点就是层级，直接使用ArrayList的层级
* @param root
* @param node
* @param level
*/
private static void addNode(TreeNode root,List<List<Integer>> node,Integer level) {
if(root==null){
return;
}
TreeNode left = root.left;
TreeNode right = root.right;
if(node.size() <= level){
node.add(new ArrayList<>());
}
node.get(level).add(root.val);
if(left!=null){
addNode(left,node,level+1);
}
if(right!=null){
addNode(right,node,level+1);
}
}
}消耗
- 执行用时 : 1 ms
- 内存消耗 : 36.5 MB
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-04-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录