My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
List<Integer> list = new ArrayList<Integer>();
while (!helper(root, list)) {
ret.add(list);
list = new ArrayList<Integer>();
}
ret.add(list);
return ret;
}
private boolean helper(TreeNode root, List<Integer> list) {
if (root == null) {
return false;
}
else if (root.left == null && root.right == null) {
list.add(root.val);
return true;
}
else {
boolean left = helper(root.left, list);
boolean right = helper(root.right, list);
if (left) {
root.left = null;
}
if (right) {
root.right = null;
}
return false;
}
}
}
自己写了出来。比较简单地 dfs
但是有个很严重的问题，为了获得最后结果，我的确把leaf给删除了。
但是题目是说， as if
所以不能改变原来的输入，模拟那个过程，获得最终结果。
而且我的复杂度比较大，时间复杂度应该是 O(n log n)
每次遍历是O(n), 然后大概有 log n 层
然后看了答案，自己写了下：
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
height(root, ret);
return ret;
}
private int height(TreeNode root, List<List<Integer>> ret) {
if (root == null) {
return -1;
}
int level = 1 + Math.max(height(root.left, ret), height(root.right, ret));
if (level >= ret.size()) {
ret.add(new ArrayList<Integer>());
}
ret.get(level).add(root.val);
return level;
}
}
他就只用一次遍历，时间复杂度是 O(n)
而且不改变原来的数据结构。
其实他用的是 backtracking,而我的算法并没有用 backtracking
所以他在深入的时候，之前的状态还能保存住。
用的就是这个 List<List<Integer>>
然后 level 就是 list 的index
所以即使在左侧深入下去，貌似右侧的那些同等深度的结点被漏掉了。
但是其实回溯的时候，因为这些结点的深度永远不会变，所以仍然可以把相应的list取出来，存进去。
之前的tree level traversal recursion 版本，也是用的类似的思想。
这就是 backtracking used in tree
在数组中我们做回溯，也是用一个list
list.add(i);
dfs();
list.remove(list.size() - 1);
在树的话差不多，需要一个容器记录原来的状态。
有时候还需要一个容器记录哪些结点已经被访问过了。
Anyway, Good luck, Richardo! -- 09/08/2016
