33: Binary Tree Level Order Traversal II

/************************************************************************/
        /*       33:      Binary Tree Level Order Traversal II                                         */
        /************************************************************************/
        /*
         * Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   /
  9  20
    / 
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

         * */
        
      //从叶子节点到根节点的分层遍历

 public List<List<Integer>> levelOrderBottom(TreeNode root)
        {
             List<List<Integer>> alllevelnodes = new ArrayList<List<Integer>>();
             List<List<TreeNode>> allnodes = LevelOrderTreeNodeTop(root);
             for (int i=allnodes.size()-1;i>=0;i--)
             {
                 System.out.println("---------------"+(i+1)+"层------");
                 List<Integer> tempnodes=new ArrayList<Integer>();
                 for (int j = 0; j < allnodes.get(i).size();j++ )
                 {
                     tempnodes.add(allnodes.get(i).get(j).val);
                     System.out.println("--" + allnodes.get(i).get(j).val);
                 }
                 alllevelnodes.add(tempnodes);
             }
             return alllevelnodes;
        }

        
      //从根节点点到叶子节的分层遍历得到节点序列
        public List<List<TreeNode>> LevelOrderTreeNodeTop(TreeNode rootNode)
        {
            List<List<TreeNode>> allnodes = new ArrayList<List<TreeNode>>();
            if (rootNode==null)
            {
                return allnodes;
            }
            List<TreeNode> rootlevel = new ArrayList<TreeNode>();
            rootlevel.add(rootNode);
            allnodes.add(rootlevel);
            while(true)
            {
                List<TreeNode> templevel = new ArrayList<TreeNode>();
                for (int i=0;i<allnodes.get(allnodes.size()-1).size();i++)
                {
                    if(allnodes.get(allnodes.size()-1).get(i).left!=null)
                    {
                        templevel.add(allnodes.get(allnodes.size()-1).get(i).left);
                    }
                    if(allnodes.get(allnodes.size()-1).get(i).right!=null)
                    {
                        templevel.add(allnodes.get(allnodes.size()-1).get(i).right);
                    }
                }
                if (templevel.size()<1)
                {
                    break;
                }
                allnodes.add(templevel);
            }
            return allnodes;
        }
        
        //从叶子节点到根节点的分层遍历 代码改进一些   
        public List<List<Integer>> levelOrderBottomEx(TreeNode root) {
            List<List<Integer>> container = new ArrayList<List<Integer>>();
            if (root == null) return container;
            TreeNode cur = null;
            Queue<TreeNode> sameLevel = new LinkedList<TreeNode>();
            sameLevel.add(root);
            while (!sameLevel.isEmpty()) {
                List<Integer> oneLevel = new ArrayList<Integer>();
                Queue<TreeNode> temp = new LinkedList<TreeNode>();
                while(!sameLevel.isEmpty()) {
                    cur = sameLevel.remove();
                    oneLevel.add(cur.val);
                    if (cur.left != null)  temp.add(cur.left); 
                    if (cur.right != null) temp.add(cur.right);
                }
                container.add(0,oneLevel);
                sameLevel = temp;
            }
            return container;
        }