# 背景知识：

``` public void levelOrderTraversal(TreeNode root){
if (root == null ) return;
while (!queue.isEmpty()){
TreeNode node = queue.remove();
System.out.println(node.val);
}
}```

# 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   7```

return 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<>();
while (!queue.isEmpty()){
List<Integer> resTemp = new ArrayList<>();
int size = queue.size();
for (int i = 0;i<size;i++){
TreeNode node = queue.remove();
if (node.left != null) {
}
if (node.right != null) {
}
}
}
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++){
}
return res;
}

public void levelOrderBottomHelper(TreeNode root,HashMap<Integer,ArrayList<Integer>> map,int level){
if (root == null ) return;
if (map.containsKey(level)){
}else {
ArrayList<Integer> list = new ArrayList<>();
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   7```

return 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<>();
while (!queue.isEmpty()){
List<Integer> resTemp = new ArrayList<>();
int size = queue.size();
for (int i = 0;i<size;i++){
TreeNode node = queue.remove();
if (node.left != null) {
}
if (node.right != null) {
}
}
stack.push(resTemp);
}
while (!stack.isEmpty()){
}
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--){
}
return res;
}

public void levelOrderBottomHelper(TreeNode root,HashMap<Integer,ArrayList<Integer>> map,int level){
if (root == null ) return;
if (map.containsKey(level)){
}else {
ArrayList<Integer> list = new ArrayList<>();
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<>();
if (root == null) return null;
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) ;
}
}
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   7```

return its zigzag level order traversal as:

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

0 条评论

## 相关文章

1912

1462

1052

### B树 B-树 B+树 B*树

B树 即二叉搜索树：        1.所有非叶子结点至多拥有两个儿子（Left和Right）；        2.所有结点存储一个关键字；        3...

2057

1113

961

2339

2554

25610

### 数据结构与算法 -- 二叉树链式详解（（非）/递归遍历，叶子个数，深度计算）

PS：树型结构是一种重要的非线性数据结构，教科书上一般都是树与二叉树，由此可见，树和二叉树是有区别和联系的，网上有人说二叉树是树的一种特殊形式，但经过查资料，树...

1035