首页 > 代码库 > [LeetCode]Binary Tree Level Order Traversal II
[LeetCode]Binary Tree Level Order Traversal II
题目:给定一颗二叉树,求出对其层次遍历以后的逆序输出
样例:
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 class Solution { ArrayList<List<Integer>> levelOrderList = new ArrayList<List<Integer>>(); public List<List<Integer>> levelOrderBottom(TreeNode root) { dfs(root, 0); ArrayList<List<Integer>> levelOrderReverseList = new ArrayList<List<Integer>>(); for (List<Integer> levelOrder : levelOrderList) { levelOrderReverseList.add(0, levelOrder); } return levelOrderReverseList; } public void dfs(TreeNode node, int height) { if (null == node) { return ; } if (levelOrderList.isEmpty() || levelOrderList.size()<height+1) { List<Integer> levelOrder = new ArrayList<Integer>(); levelOrder.add(node.val); levelOrderList.add(height, levelOrder); } else if (levelOrderList.size() >= height+1) { List<Integer> levelOrder = levelOrderList.get(height); levelOrder.add(node.val); } dfs(node.left, height+1); dfs(node.right, height+1); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。