题目
- 请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
示例
- 示例1
- 给定二叉树: [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
- 返回:
[
[3],
[20,9],
[15,7]
]
代码
- 递归层次遍历
class Solution {
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
dfs(root,0);
return list;
}
public void dfs(TreeNode root,int level){
if(root == null) return;
if(list.size() <= level) // 深度小于等于本层深度
list.add(new ArrayList());
if(level % 2 == 0)
list.get(level).add(root.val);
else
list.get(level).add(0,root.val);
dfs(root.left,level+1);
dfs(root.right,level+1);
}
}
代码分析
: if(level % 2 == 0)
判断层次 level 的奇偶性。奇数层使用头插法实现逆序,偶数层尾插为正序,
- 其他方法