For example:
Given binary tree
{3,9,20,#,#,15,7}
,3 / \ 9 20 / \ 15 7return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ]
confused what
"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ./** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { // Adopt levelorder traversal List<List<Integer>> result = new LinkedList<>(); if (root == null) return result; List<List<Integer>> tmp = new LinkedList<>(); List<Integer> row = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); int count = 0; int curMode = 1; // Number of nodes of current level int nxtMode = 0; // Number of nodes of next level queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.remove(); row.add(node.val); count++; // Verify if current node is the last node of the level or not if (count%curMode == 0) { tmp.add(row); row = new LinkedList<>(); count = 0; } if (node.left != null) { queue.add(node.left); nxtMode++; // Count the number of next level node } if (node.right != null) { queue.add(node.right); nxtMode++; } // When reached the end of the level, assign next mode to current mode. // Next mode then reset to 0. if (count == 0) { curMode = nxtMode; nxtMode = 0; } } // Reverse the order for (int i = tmp.size()-1; i >= 0; i--) result.add(tmp.get(i)); return result; } }
No comments:
Post a Comment