Binary Tree Longest Consecutive Sequence

题目链接：

这一个类型的题都一样用dfs，分治的思想。两种方式：一种用global variable，另一种直接把sequence的长度作为返回值，思路都一样。也可以直接在当前层对左右节点分别处理，本质和前面一样的。iteration也可以解，用stack或者queue来做，但是本质都是dfs。

public int longestConsecutive(TreeNode root) {        /* dfs         * arguments: curNode, previous value, length         * 2 chooses: 1. curNode.val >= previous_value => length + 1         *            2. curNode.val < previous_value  => length = 1         * update length each recursion: use a global variable         */         if(root == null) return 0;         dfs(root, root.val - 1, 0);         return global;    }        int global = 0;    private void dfs(TreeNode curNode, int previous_value, int len) {        // update global length        global = Math.max(global, len);        // base case        if(curNode == null) {            return;        }                if(curNode.val - previous_value == 1) len++;        else len = 1;        dfs(curNode.left, curNode.val, len);        dfs(curNode.right, curNode.val, len);    }

2.用返回值

public int longestConsecutive(TreeNode root) {        /* dfs         * arguments: curNode, previous value, length         * 2 chooses: 1. curNode.val >= previous_value => length + 1         *            2. curNode.val < previous_value  => length = 1         * update length each recursion: return the max length         */         if(root == null) return 0;         return dfs(root, root.val - 1, 0);    }        private int dfs(TreeNode curNode, int previous_value, int len) {        // base case        if(curNode == null) {            return len;        }                if(curNode.val - previous_value == 1) len++;        else len = 1;        return Math.max(len, Math.max(dfs(curNode.left, curNode.val, len), dfs(curNode.right, curNode.val, len)));    }

3.在当前层处理分别处理左右节点，这样不用传上一次的值，注意这样初始的len就是1了：

public int longestConsecutive(TreeNode root) {         if(root == null) return 0;         dfs(root, 1);         return global;    }        int global = 0;    private void dfs(TreeNode curNode, int len) {        global = Math.max(global, len);                if(curNode.left != null) {            if(curNode.val + 1 == curNode.left.val) dfs(curNode.left, len+1);            else dfs(curNode.left, 1);        }        if(curNode.right != null) {            if(curNode.val + 1 == curNode.right.val) dfs(curNode.right, len+1);            else dfs(curNode.right, 1);        }    }