首页 > 代码库 > Leetcode-Binary Tree Level Order Traversal II
Leetcode-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]]
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
Solution:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public List<List<Integer>> levelOrderBottom(TreeNode root) {12 List<List<Integer>> res = new ArrayList<List<Integer>>();13 if (root==null)14 return res;15 16 //Visit all node by using BFS.17 List<TreeNode> queue = new ArrayList<TreeNode>();18 List<Integer> depth = new ArrayList<Integer>();19 queue.add(root);20 depth.add(1);21 int index = 0;22 int curDepth = -1;23 TreeNode curNode = null;24 while (index<queue.size()){25 curNode = queue.get(index);26 curDepth = depth.get(index);27 if (curNode.left!=null){28 queue.add(curNode.left);29 depth.add(curDepth+1);30 }31 32 if (curNode.right!=null){33 queue.add(curNode.right);34 depth.add(curDepth+1);35 }36 37 index++;38 }39 40 //Get the max depth, which is the number of lists in the result.41 int maxDepth = depth.get(depth.size()-1);42 for (int i=0;i<maxDepth;i++)43 res.add(new ArrayList<Integer>());44 45 //Put the value of each node into the corresponding list in the result.46 for (int i=0;i<queue.size();i++){47 curNode = queue.get(i);48 curDepth = depth.get(i);49 index = maxDepth-curDepth;50 List<Integer> tempList = res.get(index);51 tempList.add(curNode.val);52 }53 54 return res;55 }56 }
Using BFS to visit and record every tree node and its depth. Then put the value in each tree node into corresponding level list.
Leetcode-Binary Tree Level Order Traversal II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。