BinaryTreePaths [source code]
public class BinaryTreePaths {
static
/******************************************************************************/
public class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) return res;
dfs(root, res, "");
return res;
}
private void dfs(TreeNode root, List<String> ls, String accum) {
if (root == null) return;
accum += (accum.length() == 0 ? "" : "->") + root.val;
if (root.left == null && root.right == null) {
ls.add(accum);
return;
}
dfs(root.left, ls, accum);
dfs(root.right, ls, accum);
}
}
/******************************************************************************/
public static void main(String[] args) {
BinaryTreePaths.Solution tester = new BinaryTreePaths.Solution();
}
}
DFS 问题很多时候最简单的做法就是让 helper 是 void, 这样把所有的变化都反映在 global 里面: 利用Side Effect;
这个题目本身是不需要用 recursion 来理解的, 因为不存在什么 DP Property; 需要注意的是, 这个问题虽然不难, 不过这个问题的解法我们之前并没有总结过: 在 DFS 思路理解 tree 问题的时候, 还有一个常见的技巧就是 accum. 其实严格来说这题这的这个 string 并不能算作是 accum, 更像是一个 tag: 每一个 node 都有一个自己独特的tag, 类似之前的 height 一样; 这个东西具体怎么总结还没有想好, 反正这个tag 跟之前学 ocaml 的时候的 accum 感觉有一定区别;
base case 的选择: 判 leaf 而不是 Null;
这个题目刚开始只选择了判断 Null, 后来发现这个并不够. 这个题目, add 的点是在 leaf 而不是等到已经走到了 Null 了; 所以对于有两个 child 都是 Null 的 node 和只有一个 child 是 Null 的 node 要分开处理(也正是因为这种只有一个 Null 的node, 我们的 Null 的 base case 判断仍然需要保留);
main call 的参数怎么选择
这个是一个一直被忽视的问题, 这里就看出来了. 刚开始我main call arg3一直使用的是root.val + ""这样的, 但是这个理解就有问题. DFS 或者说 recursion 本身是一个自成一派的整体, 所有的操作都必须保证在 recursion 的内部完成;
比如:
1
/ \
2 3
这么一个简单的 tree. 首先你要想好你每一个 node 的 tag 是什么. 比如你这里1的 tag 应该是"1", 2的tag 应该是"1->2": 更进一步, 虽然我们知道了2的 tag 是这个, 那么dfs(2)的 arg3应该是什么? 是"1"还是"1->2"? 要知道这个 arg3是1给出的, 所以显然这个 arg3是"1"更合理, 这样1就不用站在2的 subtree 外面还要判断2的 val;
类似的, call to 1的 arg3也应该不包含1.val;
最后的速度是15ms (96%), 算是一个最优解了;
这个是一个人提出的问题:
I see people interview FB meet this question in phone screen. It's simple. But interviewer will ask you about time complexity. The worst case is not that straight-forward. You should try to construct a tree with that 'worst case'. Assume the number of treeNode is n, you need to provide the big O notation of n.
这个是 discussion 里面提到的一个有趣的观点:
The time complexity for the problem should be O(n), since we are basically visiting each node in the tree. Yet an interviewer might ask you for further optimization when he or she saw a string concatenation. A string concatenation is just too costly. A StringBuilder can be used although a bit tricky since it is not immutable like string is.
2018-05-02 20:35:11 这里的讨论都有点问题, 首先最坏情况, 比如一个向左的line, 每一个node要么是两个child, 要么是0个child, 所以是一个类似两条左行的平行线这样的树. 如果算上string操作的复杂度, 最后复杂度其实是N^2, 这个很好证明; 另外StringBuilder并不能帮助改变这个情况: 你最后要add一个path的时候, 还是要有一个O(length of string = len_of_path)的操作, 所以最后这个时间复杂度并无法避免;
When using StringBuilder, We can just keep track of the length of the StringBuilder before we append anything to it before recursion and afterwards set the length back. Another trick is when to append the "->", since we don't need the last arrow at the end of the string, we only append it before recurse to the next level of the tree. Hope the solution helps!
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder();
helper(res, root, sb);
return res;
}
private void helper(List<String> res, TreeNode root, StringBuilder sb) {
if(root == null) {
return;
}
int len = sb.length();
sb.append(root.val);
if(root.left == null && root.right == null) {
res.add(sb.toString());
} else {
sb.append("->");
helper(res, root.left, sb);
helper(res, root.right, sb);
}
sb.setLength(len);
}
意思是他觉得这个问题如果你引入了builder, 那么还是可以用 accum 而不是tag 的思路来做的; 使用 accum 的一个问题在于, 每一次你退出一个 subtree的时候, 你要撤销在这个 subtree 内部产生的变化: 比如你从root.left退出了, 那么进入root. right 之前, 你要撤销在 left 里面完成的变化; 这里完成这个撤销的操作很简单, 直接就是进入 left 之前记录 len, 然后退出 left 之后, 还原到 len 就行了, 这个技巧也是因为builder 本身的特性决定的;
底下有人认为他对于复杂度的分析不对:
@yfcheng For this kinds of problem that uses DFS to find all the paths, the time complexity is usually O(max_length_of_each_path * max_number_of_valid_paths) rather than O(n), as each time you find a valid path, you need to copy the array first before storing it in the result. Even if you use StringBuilder, toString creates a copy of the wrapped char array and is not an O(1) operation.
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/lang/StringBuilder.java#StringBuilder.toString()
So the time complexity of your solution is still O(n^2) --- max_length_of_each_path = O(n), max_number_of_leaves = O(n). This is a very loose bound and the actual time complexity may be smaller, but not really O(n). The constant in your case should be much smaller than the posted solution.
我对此给出了更好的解释:
First let's work on the balanced tree situation:
It should be obvious to see now that each node will contribute to the total time cost an amount of length of the path from the root to this node. The problem is to see how to sum up these paths' lengths for N nodes altogether.
Denote the time complexity for N nodes as T(N).
Suppose we do have that balanced tree now (and also N is 2^N-1 for simplicity of discussion). Amd we know that N/2 nodes lie at the leaf/deepest level of the BST since it's balanced binary tree.
We easily have this recurrence formula:T(N) = T(N/2) + (N/2) * lgN
Which means, we have N nodes, with half lying on the deepest (the lgNth) level. The sum of path lengths for N nodes equals to sum of path lengths for all nodes except those on the lgN-th level plus the sum of path lengths for those nodes on the lgN-th level.
This recurrence is not hard to solve. I did not try to work out the exact solution since the discussion above in itself are in essence a little blurry on corner cases, but it is easy to discover that T(N) = O(NlgN).
The problem left here now, is a balanced tree the best-case or the worst-case? I was convinced it was the worst case before I doodled some tree up and found otherwise.
The worst case is actually when all nodes lie up to a single line like a linked list, and the complexity in this case is easily calculable as O(N^2). But how do we prove that?
the proof is easier than you think. Just use induction. Suppose we have N - 1 nodes in a line, and by inductive hypothesis we claim that this tree is the max-path-sum tree for N-1 nodes. We just have to prove that the max-path-sum tree for N nodes is also a single line. How do you prove it? Well suppose that you see the N-1-node line here, and you want to add the N-th node, where would you put it? Of course the deepest level so that the new node gets maximum depth.
Proving that the best case is the balanced tree can be a little trickier. By some definition, A tree where no leaf is much farther away from the root than any other leaf. Suppose we define much farther as like 2 steps farther.
Then for the purpose of contradiction, suppose the min-path-sum tree for N nodes is not balanced, then there is a leaf A that is at least 2 steps further to the root than another leaf B. Then we can always move A to be the direct descendant of B (since B is leaf, there is an opening) resulting in a tree with smaller sum of paths. Thus the contradiction.
This proof is a little informal, but I hope the idea is clear.
In conclusion, the complexity of this program is Ω(NlgN) ~ O(N^2).
不过后来思考了一下, 好像这个算法的时间复杂度很大程度上是因为String immutability造成的重复 pass 导致的. 如果用 builder 可能来解决这个问题? 不过如果用 builder, 那么思路就是 accum 了. 用 accum 来模拟一个 tag 的功能的时候, 注意exit subtree的时候要撤销对 accum , 也就是这里的 builder 的更改;
这个是discussion一个没有 helper 的版本:
public List<String> binaryTreePaths(TreeNode root) {
List<String> paths = new LinkedList<>();
if(root == null) return paths;
if(root.left == null && root.right == null){
paths.add(root.val+"");
return paths;
}
for (String path : binaryTreePaths(root.left)) {
paths.add(root.val + "->" + path);
}
for (String path : binaryTreePaths(root.right)) {
paths.add(root.val + "->" + path);
}
return paths;
}
这个想法是好的, 不过感觉这个写法最后的空间复杂度很高; 事实上, 非常非常高, 因为每一个res list的空间复杂度已经是O(N^2)了, 然后你有 N 个 node, 所以最后的空间复杂度可能有O(N^3);
Problem Description
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
["1->2->5", "1->3"]
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Difficulty:Easy
Category:Algorithms
Acceptance:37.75%
Contributor: LeetCode
Companies
google apple facebook
Related Topics
tree depth-first search
Similar Questions
Path Sum II