首页 > 代码库 > [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);
		}
	}