来自Leetcode第107题二叉树的层次遍历II
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
Collections.reverse()
最简单的是按照上一次的写法,加上Collections.reverse()即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> ans = new LinkedList<List<Integer>>(); if (root == null) return ans;
Queue<TreeNode> tree = new LinkedList<TreeNode>(); tree.add(root); int level = 0; while ( !tree.isEmpty() ) { ans.add(new ArrayList<Integer>()); int level_length = tree.size(); for(int i = 0; i < level_length; ++i) { TreeNode p1 = tree.remove(); ans.get(level).add(p1.val); if (p1.left != null) tree.add(p1.left); if (p1.right != null) tree.add(p1.right); } level++; } Collections.reverse(ans); return ans; }
|
DFS
来自题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); DFS(root, 0, ans); return ans; }
private void DFS(TreeNode root, int level, List<List<Integer>> ans) { if (root == null) { return; } if (ans.size() <= level) { ans.add(0, new ArrayList<>()); } ans.get(ans.size() - 1 - level).add(root.val);
DFS(root.left, level + 1, ans); DFS(root.right, level + 1, ans); }
|
BFS
这个写法和102题没啥区别,就是把结点插在了头部,但是为啥用LinkedList的addfirst不行?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| public List<List<Integer>> levelOrderBottom(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); List<List<Integer>> ans = new LinkedList<List<Integer>>(); if (root == null) return ans; queue.offer(root); while (!queue.isEmpty()) { int levelNum = queue.size(); List<Integer> subList = new LinkedList<Integer>(); for (int i = 0; i < levelNum; i++) { TreeNode curNode = queue.poll(); if (curNode != null) { subList.add(curNode.val); queue.offer(curNode.left); queue.offer(curNode.right); } } if (subList.size() > 0) { ans.add(0, subList); } } return ans; }
|