LeetCode 102 & 103 ＆107 & 637. Binary Tree Level Order Traversal
原创LeetCode 102 & 103 ＆107 & 637. Binary Tree Level Order Traversal
原创
背景知识：
层序遍历二叉树
最为经典的解法就是借助队列，方法如下：
public void levelOrderTraversal(TreeNode root){
if (root == null ) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode node = queue.remove();
System.out.println(node.val);
if (node.left !=null) queue.add(node.left);
if (node.right !=null) queue.add(node.right);
}
}102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its level order traversal as:
[
[3],
[9,20],
[15,7]
]题目大意：层序遍历一个二叉树
解法一：
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null ) return null;
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
List<Integer> resTemp = new ArrayList<>();
int size = queue.size();
for (int i = 0;i<size;i++){
TreeNode node = queue.remove();
resTemp.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(resTemp);
}
return res;
}解法二：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
levelOrderBottomHelper(root,map,1);
for (int i = 1 ;i <=map.size() ;i++){
res.add(map.get(i));
}
return res;
}
public void levelOrderBottomHelper(TreeNode root,HashMap<Integer,ArrayList<Integer>> map,int level){
if (root == null ) return;
if (map.containsKey(level)){
map.get(level).add(root.val);
}else {
ArrayList<Integer> list = new ArrayList<>();
list.add(root.val);
map.put(level,list);
}
levelOrderBottomHelper(root.left,map,level+1);
levelOrderBottomHelper(root.right,map,level+1);
}107.Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]解法一：
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null ) return res;
Stack<List<Integer>> stack = new Stack<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
List<Integer> resTemp = new ArrayList<>();
int size = queue.size();
for (int i = 0;i<size;i++){
TreeNode node = queue.remove();
resTemp.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
stack.push(resTemp);
}
while (!stack.isEmpty()){
res.add(stack.pop());
}
System.out.println(res);
return res;
}解法二：
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
levelOrderBottomHelper(root,map,1);
for (int i = map.size() ;i > 0 ;i--){
res.add(map.get(i));
}
return res;
}
public void levelOrderBottomHelper(TreeNode root,HashMap<Integer,ArrayList<Integer>> map,int level){
if (root == null ) return;
if (map.containsKey(level)){
map.get(level).add(root.val);
}else {
ArrayList<Integer> list = new ArrayList<>();
list.add(root.val);
map.put(level,list);
}
levelOrderBottomHelper(root.left,map,level+1);
levelOrderBottomHelper(root.right,map,level+1);
}637. Average of Levels in Binary Tree
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input:
3
/ \
9 20
/ \
15 7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].题目大意：对二叉树的每一层的节点取平均值。
解法：
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
Queue<TreeNode> queue= new LinkedList<>();
if (root == null) return null;
queue.add(root);
while (!queue.isEmpty()){
int n = queue.size();
double sum = 0.0;
for (int i = 0 ; i < n;i++){
TreeNode temp = queue.remove();
sum += temp.val;
if (temp.left != null) queue.add(temp.left) ;
if (temp.right != null) queue.add(temp.right);
}
res.add(sum/n);
}
return res;
}103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]题目大意：之字形的遍历一个二叉树。
解法一：
在102题的基础上，写一个LinkedList的reverse函数将奇数的结果翻转一下就可以了
总结:
这几个题目的思路有相同之处，如果涉及到对于二叉树的每一层的数据进行处理，上述解法是一个非常典型的解决方式，即在while里面加上一个for循环，每次for循环结束都是将某一行的数据处理完。还有一种方法是采用HashMap，让level作为key值，这样每一个节点都会记录他所在的层数。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。