298. Binary Tree Longest Consecutive Sequence QuestionEditorial Solution

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.

2.算法
我一开始理解错题一了，我以为consecutive sequence可以从上往下看或者从下往上看。做了那个
这道题可以从任意点开始，因此每个点都有可能是答案。
postorder 或者preorder 都能做

 public class Solution {  
   public int max = 0;  
   public int longestConsecutive(TreeNode root) {  
     dfs(root);  
     return max;  
   }  
   public int dfs(TreeNode root) {  
     int ans = 0;  
     if(root == null)  
       return ans;  
     int left = dfs(root.left);  
     int right = dfs(root.right);  
     if(root.left!=null&&root.left.val == root.val+1)  
         ans = left+1;  
     if(root.right!=null&&root.right.val == root.val+1)  
         ans = Math.max(ans, right+1);  
     if(ans==0)  
       ans++;  
     // System.out.println(ans);  
     max = Math.max(ans, max);  
     return ans;  
   }  
 }  

如果是consecutive sequence可以从上往下看或者从下往上看:

 public int max = 0;  
   public int longestConsecutive(TreeNode root) {  
     dfs(root);  
     return max;  
   }  
   public int[] dfs(TreeNode root) {  
     //ans[0] is increasing number, ans[1] is decreasing number  
     int[] ans = new int[2];  
     if(root == null)  
       return ans;  
     int[] left = dfs(root.left);  
     if(root.left!=null){  
       if(root.left.val == root.val-1)  
         ans[0] = left[0];  
       if(root.left.val == root.val+1)  
         ans[1] = left[1];  
     }  
     int[] right = dfs(root.right);  
     if(root.right!=null){  
       if(root.right.val == root.val-1)  
         ans[0] = Math.max(ans[0], right[0]);  
       if(root.right.val == root.val+1)  
         ans[1] = Math.max(ans[1], right[1]);  
     }  
     ans[0]++;ans[1]++;  
     max = Math.max(max,Math.max(ans[1], ans[0]));  
     return ans;  
   }  

320. Generalized Abbreviation

1.题意

Write a function to generate the generalized abbreviations of a word.

Example:

Given word = "word", return the following list (order does not matter):

 ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]  

例如result一开始为一个空list，这时候加[1],result 变成[[], [1]]. i变成2时候，对与result里边所有list 加2，因此result变成[[],[1],[2],[1,2]]

对于这个题，
可以首先变1位，然后加到list中["word", "1ord", "w1rd", "wo1d", "wor1"]

然后对于list里边已经变过1位的，再变1位，变的这位应该在原来那个数字后边，这样才能避免重复["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1"]，

按照这个方法对["2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1"]再变1位 ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1","2r1", "3d", "w3"]

最后对["2r1", "3d", "w3"]再变1位得到结果。

 public class Solution {  
   List<String> ans = new ArrayList<>();  
   public List<String> generateAbbreviations(String word) {  
     helper(word,0);   
     return ans;  
   }  
   public void helper(String word,int i){  
     ans.add(word);  
     for(; i <word.length(); i++){  
       if(!Character.isDigit(word.charAt(i))){  
         int[] ii = new int[1];  
         ii[0] = i;  
         helper(abbreviate(word,ii),ii[0]);  
       }  
     }  
   }  
   public String abbreviate(String s, int[] ii){  
     int i = ii[0];  
     int p1 = i-1;  
     while(p1 >=0 && Character.isDigit(s.charAt(p1)))  
       p1--;  
     int num = 0;  
     if(p1!=i-1)  
       num=Integer.valueOf(s.substring(p1+1,i));  
     num++;  
     ii[0]=p1+1;  
     return s.substring(0,p1+1)+ String.valueOf(num) + (i==s.length()?"":s.substring(i+1));  
   }  
 }  

方法二：
对于word的每一位，都可以abbreviate或者不abbreviate。结果长度：2^n

引用：https://discuss.leetcode.com/topic/32270/java-backtracking-solution

这种方法其实是在构造每个abbreviation，而不是从原有的word中修改获得abbreviation。

The idea is: for every character, we can keep it or abbreviate it. To keep it, we add it to the current solution and carry on backtracking. To abbreviate it, we omit it in the current solution, but increment the count, which indicates how many characters have we abbreviated. When we reach the end or need to put a character in the current solution, and count is bigger than zero, we add the number into the solution.

 public List<String> generateAbbreviations(String word){  
     List<String> ret = new ArrayList<String>();  
     backtrack(ret, word, 0, "", 0);  
     return ret;  
   }  
   private void backtrack(List<String> ret, String word, int pos, String cur, int count){  
     if(pos==word.length()){  
       if(count > 0) cur += count;  
       ret.add(cur);  
     }  
     else{  
       backtrack(ret, word, pos + 1, cur, count + 1);  
       backtrack(ret, word, pos+1, cur + (count>0 ? count : "") + word.charAt(pos), 0);  
     }  
   }