298. Binary Tree Longest Consecu

Description

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).

Example 1:

Input:

image.png
Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.</pre>

Example 2:

Input:

image.png

**Output: 2

Explanation:** Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.

Solution

Bottom-up DFS, O(n), S(h)

返回满足X条件的最长Path len。这类题目着实不少，都可以用返回int[]这种方式来解决。其实也可以添加一个static int maxLen，但我实在不喜欢这种写法，所以还是返回int[]吧，麻烦点就麻烦点好了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return dfs(root)[1];
    }
    // res[0] is consecutive path len from root
    // res[1] is max consecutive path len currently met
    private int[] dfs(TreeNode root) {
        if (root.left == null && root.right == null) {
            return new int[] {1, 1};
        }
        
        int[] res = new int[] {1, 1};   // single node path
        
        if (root.left != null) {        // try to connect left child
            int[] left = dfs(root.left);
            if (isConsecutive(root, root.left)) {
                res[0] = Math.max(left[0] + 1, res[0]);
            }
            res[1] = Math.max(left[1], res[1]);
        }
        
        if (root.right != null) {       // try to connect right child
            int[] right = dfs(root.right);
            if (isConsecutive(root, root.right)) {
                res[0] = Math.max(right[0] + 1, res[0]);
            }
            res[1] = Math.max(right[1], res[1]);
        }
        
        res[1] = Math.max(res[0], res[1]);
        return res;
    }
    
    private boolean isConsecutive(TreeNode p, TreeNode q) {
        return p.val + 1 == q.val;
    }
}

Top-down DFS, O(n), S(h)

没看太懂...

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int longestConsecutive(TreeNode root) {
        return dfs(root, null, 0);
    }
    
    private int dfs(TreeNode curr, TreeNode parent, int len) {
        if (curr == null) {
            return len;
        }
        
        len = (parent != null && curr.val == parent.val + 1) ?
            len + 1 : 1;
        return Math.max(len, Math.max(
            dfs(curr.left, curr, len), dfs(curr.right, curr, len)));
    }
}