3ms Java solution with comments, no recursion


  • 0
    B
        /*
        * the main idea is to search from the root, store the nodes of the same rank in 
        * an ArrayList and use that for the reference of the next rank.
        */
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            if(root==null) return new ArrayList<List<Integer>>();
            //whole is the result ArrayList of TreeNode type.
            List<List<TreeNode>> whole = new ArrayList<List<TreeNode>>();
            //level represents each rank level of whole.
            List<TreeNode> level = new ArrayList<TreeNode>();
            //level begins from root.
            level.add(root);
            //newLevel is the next rank of level.
            List<TreeNode> newLevel = new ArrayList<TreeNode>();
            while(!level.isEmpty()){
                whole.add(level);
                for(TreeNode node : level){
                    TreeNode left = node.left;
                    TreeNode right = node.right;
                    if(left!=null) newLevel.add(left);
                    if(right!=null) newLevel.add(right);
                }
                level = newLevel;
                newLevel = new ArrayList<TreeNode>();
            }
            return getReverseNodeValue(whole);
        }
        /*
        * The following method will turn the TreeNode type ArrayList to Integer value type ArrayList.
        */
        private List<List<Integer>> getReverseNodeValue(List<List<TreeNode>> whole){
            if(whole.isEmpty()) return null;
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            //The following loop reverse the rank order in BST "whole".
            for(int i = whole.size() - 1; i >= 0; i--){
                List<Integer> resElement = new ArrayList<Integer>();
                //Loop through a rank to get all the elements from left to right.
                for(int j = 0; j < whole.get(i).size(); j++){
                    resElement.add(whole.get(i).get(j).val);
                }
                res.add(resElement);
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.