首页 > 代码库 > Binary Tree Level Order Traversal II
Binary Tree Level Order Traversal II
这道题A的略烦
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]]
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 int height;12 TreeNode root;13 14 public List<List<Integer>> levelOrderBottom(TreeNode root) {15 this.height = getDepth(root);//获取树的高度16 this.root = root;17 18 List<List<Integer>> list = new ArrayList<List<Integer>>();19 for(int i = 0; i < height; i++){20 List<Integer> element = new ArrayList<Integer>();21 list.add(element);22 }//this.height没有错23 preOrder(root, list);24 25 return list;26 }27 28 /**29 * node在tree中高度30 * @param root31 * @param node32 * @return33 */34 public int getDepth(TreeNode root, TreeNode node){35 if(null == root)36 return -Integer.MAX_VALUE;37 if(node == root)38 return 1;39 else{40 int maxl = getDepth(root.left, node);41 int maxr = getDepth(root.right, node);42 if(maxl > maxr)43 return maxl + 1;44 else45 return maxr + 1;46 }47 }48 /**49 * 获取树的高度50 * @param root51 * @return52 */53 public int getDepth(TreeNode root){54 if(null == root){55 return 0;56 }else{57 int maxl = getDepth(root.left);58 int maxr = getDepth(root.right);59 return maxl>maxr ? (maxl + 1):(maxr + 1);60 }61 }62 /**63 * 前序遍历树64 * @param root65 */66 public void preOrder(TreeNode root, List<List<Integer>> list){67 if(null != root){68 int height = getDepth(this.root, root);69 List<Integer> element = list.get(this.height - height);70 element.add(root.val);71 preOrder(root.left, list);72 preOrder(root.right, list);73 }74 }75 }
Binary Tree Level Order Traversal II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。