首页 > 代码库 > 33: Binary Tree Level Order Traversal II
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; }
33: Binary Tree Level Order Traversal II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。