257. Binary Tree Paths

题目：

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

All root-to-leaf paths are:

["1->2->5", "1->3"]

链接： http://leetcode.com/problems/binary-tree-paths/

一刷

刚刚复习了树的后序遍历，先尝试用iterative方法，但是performance并不是很理想

 1 class Solution:
 2     # @param {TreeNode} root
 3     # @return {string[]}
 4     def binaryTreePaths(self, root):
 5         if not root:
 6             return []
 7         path = [root]
 8         prev = None
 9         cur = path[-1]
10         result = []
11         while path:
12             cur = path[-1]
13             if not prev or prev.left == cur or prev.right == cur:
14                 if cur.left:
15                     path.append(cur.left)
16                 elif cur.right:
17                     path.append(cur.right)
18                 else:
19                     result.append('->'.join([str(a.val) for a in path]))
20                     path.pop()
21             elif cur.left == prev:
22                 if cur.right:
23                     path.append(cur.right)
24                 else:
25                     path.pop()
26             elif cur.right == prev:
27                 path.pop()
28             prev = cur
29         return result

其实与树的后序遍历唯一区别是第19行，如果没有19行，就是完全的树的后序遍历，也就可以refactor到此链接里的alternative解法，但是正是有了这一行，就不能refactor。原因是，我们需要把所有节点都pop，但是只有叶节点需要放进result。

下一次需要用recursive解法，希望performance变好。

5/8/2017

算法班

很多之前会做，或者有思路的题目现在居然都不会做了。这道题的思路是每个节点产生的子树list就是当前val和每个左子树与每个右子树list一起产生的新的list

时间复杂度？

 1 public class Solution {
 2     /**
 3      * @param root the root of the binary tree
 4      * @return all root-to-leaf paths
 5      */
 6     public List<String> binaryTreePaths(TreeNode root) {
 7         List<String> ret = new ArrayList<String>();
 8 
 9         if (root == null) {
10             return ret;
11         }
12         if (root.left == null && root.right == null) {
13             ret.add(root.val + "");
14         }
15         List<String> left = binaryTreePaths(root.left);
16         List<String> right = binaryTreePaths(root.right);
17         
18         for (String s: left) {
19             ret.add(root.val + "->" + s);
20         }
21         for (String s: right) {
22             ret.add(root.val + "->" + s);
23         }
24         return ret;
25     }
26 }

别人的答案：

https://discuss.leetcode.com/topic/21474/accepted-java-simple-solution-in-8-lines

https://discuss.leetcode.com/topic/23047/clean-java-solution-accepted-without-any-helper-recursive-function

用python的各种dfs, bfs

https://discuss.leetcode.com/topic/21559/python-solutions-dfs-stack-bfs-queue-dfs-recursively

用StringBuilder，记录改变之前的长度

https://discuss.leetcode.com/topic/23114/java-solution-using-stringbuilder-instead-of-string-manipulation

 1 public class Solution {
 2     public List<String> binaryTreePaths(TreeNode root) {
 3         List<String> rst = new ArrayList<String>();
 4         if(root == null) return rst;
 5         StringBuilder sb = new StringBuilder();
 6         helper(rst, sb, root);
 7         return rst;
 8     }
 9     
10     public void helper(List<String> rst, StringBuilder sb, TreeNode root){
11         if(root == null) return;
12         int tmp = sb.length();
13         if(root.left == null && root.right == null){
14             sb.append(root.val);
15             rst.add(sb.toString());
16             sb.delete(tmp , sb.length());
17             return;
18         }
19         sb.append(root.val + "->");
20         helper(rst, sb, root.left);
21         helper(rst, sb, root.right);
22         sb.delete(tmp , sb.length());
23         return;
24         
25     }
26 }