首页 > itarticle > p107

p107

admin 11月 12, 2020 0

LeetCode p107 Binary Tree Level Order Traversal II 题解

1.题目：

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,null,null,15,7],

/
9 20
/
15 7
return its bottom-up level order traversal as:

[
[15,7],
[9,20],
[3]
]

题意：

将一个树倒过来以列表输出。从深到浅。

2.解题思路:

dp，然后将列表反转过来。

3.代码

[title] [] [url] [link text]

 

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class  {
    public List<List<Integer>> ans = new ArrayList<List<Integer>>();

	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		dp(root, 0);
		int s = ans.size();
		List<List<Integer>> a = new ArrayList<List<Integer>>();
		for (int i = s - 1; i > -1; i--) {
			if (ans.get(i).size() > 0)
				a.add(ans.get(i));
		}
		return a;

	}

	public void dp(TreeNode root, int n) {
		if (root == null)
			return;
		if (ans.size() <= n)
			ans.add(new ArrayList<Integer>());
		ans.get(n).add(root.val);
		dp(root.left, n + 1);
		dp(root.right, n + 1);

	}
}

4.一些总结：