Binary Tree Longest Consecutive Sequence.java

M

屌炸天的4行代码。Divide and Conquer

主要想法：    
Recursive用好。首先在这个level比一比，可否成。   
不成的话，另立门户, count = 1。    
然后左右开弓。再把结果拿过来比较一下就好了。

```
/*
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.

Tags:Tree
Similar Problems: (H) Longest Consecutive Sequence

*/

/*
Attemp2: http://www.cnblogs.com/jcliBlogger/p/4923745.html.
The original solution has just 4 lines of C++ code. That hurts.
The concept is very much similar as my attempt1, though the code is more clear with recursive call
1. pass alone a depth. 
2. if consecutive, depth++; else, start from depth 1
3. Go deeper on both left, and right; both with new depth: currDepth;
4. Compare the Max of currDept, left's return, right's return.
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int longestConsecutive(TreeNode root) {
        return recursiveHelper(root, null, 0);
    }

    public int recursiveHelper(TreeNode curr, TreeNode parent, int depth) {
    	if (curr == null) {
    		return 0;
    	} 
    	int currDepth = 0;
    	if (parent != null && parent.val + 1 == curr.val) {
    		currDepth = depth + 1;
    	} else {
    		currDepth = 1;
    	}
    	return Math.max(currDepth, Math.max(recursiveHelper(curr.left, curr, currDepth), recursiveHelper(curr.right, curr, currDepth)));
    }
}


/*
Attemp1, failed.
Thoughts:
Seems like backtracking: we find the lowest level, then return depth, and add it on parent's record if consectutive.
always record a max value.
If node.left != null || node.right != null, if consecutive, node.depth = node.child.depth  +1
If node.left == null && node.right == null, return 1;


public class Solution {
	private int max = Integer.MIN_VALUE;
    public int longestConsecutive(TreeNode root) {
    	dfsOnNode(root);
        return max;
    }

    public int dfsOnNode(TreeNode root) {
    	int depth = 0;
    	int localMax = Integer.MIN_VALUE;
        if (root == null) {
        	return depth;
        }
        if (root.left == null && root.right == null) {//ON:right4,
        	depth++;
        	return depth;
        }
        if (root.right != null) {//root.right = 3, right4,
        	int childDepth = longestConsecutive(root.right);//ON: 3, right4
        	if (root.val + 1 == root.right.val) {//3+1=4
        		depth = childDepth + 1;//1+1=2
        	} else {
        		depth = 1;
        	}
        }
        localMax = Math.max(localMax, depth);
        if (root.left != null) {
        	int childDepth = longestConsecutive(root.left);
        	if (root.val + 1 == root.left.val) {
        		depth = childDepth + 1;
        	} else {
        		depth = 1;
        	}
        }
        localMax = Math.max(localMax, depth);
        max = Math.max(max, localMax);
        return localMax;
    }
}
*/
```