【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]] 

  
 

  
1
  
2
 

示例 2:

输入: [3,9,20,1,2,15,7]
输出: [[1,2,15,7],[9,20],[3]]  

  
 

  
1
  
2
 

解题源码

另外还有方式，使用队列是没问题的，在这里使用递归方式进行

方法一

源码

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; }
}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
 

消耗

• 执行用时 : 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
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
 

消耗

• 执行用时 : 1 ms
• 内存消耗 : 36.5 MB

文章来源: blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_26525215/article/details/116300989