Gardening版四月主题活动 【人间四月天 】# gardening - 拈花惹草
C*n
1 楼
Q: You are given a binary tree in which each node contains a value Design an
algorithm to print all paths which sum up to that value Note that it can be
any path in the tree - it does not have to start at the root.
其实这个题本身就说的不清楚，我看了一下答案解析，发现题意是：给你一个二叉树，
每个节点都有一个数，再给你一个sum，求树中所有和为sum的路径，路径的开始可以
不为root。
答案中给出的解法号称O(nlgn)的时间复杂度（其实就是最直觉化的做法，每个节点都
DFS），但是我感觉答案对时间复杂度的分析有问题，因为他分析的时候有个条件是：
There are 2^r nodes at level r。我感觉他分析的这个不是最坏情况，最坏情况应该
是每一个level只有一个节点，时间复杂度为O(n^2)
求问刷过Cracking Coding Interview的前辈，这个题的答案是否错了？另外有没有低
于O(n^2)的解法？
algorithm to print all paths which sum up to that value Note that it can be
any path in the tree - it does not have to start at the root.
其实这个题本身就说的不清楚，我看了一下答案解析，发现题意是：给你一个二叉树，
每个节点都有一个数，再给你一个sum，求树中所有和为sum的路径，路径的开始可以
不为root。
答案中给出的解法号称O(nlgn)的时间复杂度（其实就是最直觉化的做法，每个节点都
DFS），但是我感觉答案对时间复杂度的分析有问题，因为他分析的时候有个条件是：
There are 2^r nodes at level r。我感觉他分析的这个不是最坏情况，最坏情况应该
是每一个level只有一个节点，时间复杂度为O(n^2)
求问刷过Cracking Coding Interview的前辈，这个题的答案是否错了？另外有没有低
于O(n^2)的解法？
