二叉树的层序遍历,普遍做法是用队列bfs;在某些需要记录level的题型中,dfs也是一种不错的方法。
一,给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。LeetCode102
示例:
二叉树:[3,9,20,null,null,15,7]
,
3
/
9 20
/
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
不同于普通的层序遍历,现在需要分层,因此出队列的时候需要将同一层的一起出队,数量为出队前的队列长度。比较简单,不再赘述。
public List<List<Integer>> levelOrder(TreeNode root) { if(root==null) return new ArrayList<>(); List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); queue.add(root); while (!queue.isEmpty()) { List<Integer> list = new ArrayList<>(); int n = queue.size(); for (int i = 0; i < n; i++) { //同一层的节点出列 TreeNode top = queue.poll(); //poll()结合了C++中的top(),pop(). list.add(top.val); if (top.left != null) queue.add(top.left); if (top.right != null) queue.add(top.right); } res.add(list); } return res; }
二,给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)LeetCode107
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/
9 20
/
15 7
返回其自底向上的层次遍历为:
[
[15,7],
[9,20],
[3]
]
递归在于要记录节点所在的level,以便回溯时添加进对应level的数组中。
public List<List<Integer>> levelOrderBottom(TreeNode root) { if(root==null) return new ArrayList<>(); List<List<Integer>> res = new ArrayList<>(); dfs(root, 0, res); return res; } public void dfs(TreeNode root, int level, List<List<Integer>> res) { if(level>=res.size()) //新的一层,需要对res扩容 res.add(0, new ArrayList<Integer>()); //由于倒序,新数组要添加在已有数组上方 res.get(res.size()-level-1).add(root.val); //添加进对应层的数组中 if(root.left!=null) dfs(root.left, level + 1, res); if(root.right!=null) dfs(root.right, level + 1, res); }
总结:这两题都可以用bfs和dfs的方法。
107bfs:res.add(list);改为res.add(0,list);
102dfs:res.add(0,new ArrayList<Integer>());改为res.add(new ArrayList<Integer>());且res.get(res.size()-level-1)改为res.get(level).