Binary Tree Longest Consecutive Sequence

svtter 发布于2019-08-14 17:19 / 2216人阅读

摘要：题目链接这一个类型的题都一样用，分治的思想。两种方式一种用，另一种直接把的长度作为返回值，思路都一样。也可以解，用或者来做，但是本质都是。用用返回值在当前层处理分别处理左右节点，这样不用传上一次的值，注意这样初始的就是了

Binary Tree Longest Consecutive Sequence

题目链接：https://leetcode.com/problems...

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

    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);
        }
    }

GPU云服务器云服务器 binary-tree binary-search-tree Longest Sequence

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66560.html

[Leetcode] Binary Tree Longest Consecutive Sequenc

摘要：递归法复杂度时间空间思路因为要找最长的连续路径，我们在遍历树的时候需要两个信息，一是目前连起来的路径有多长，二是目前路径的上一个节点的值。代码判断当前是否连续返回当前长度，左子树长度，和右子树长度中较大的那个 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

xi4oh4o 2019-08-14 16:16 评论0 收藏0
298. Binary Tree Longest Consecutive Sequence

摘要：题目解答分治，一种不带返回值，但需要用全局变量，一种带返回值，不用全局变量有全局变量题目：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 a...

荆兆峰 2019-08-14 14:15 评论0 收藏0
[LeetCode] 549. Binary Tree Longest Consecutive Se

Problem Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree. Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] ...

bingchen 2019-08-19 11:11 评论0 收藏0
[Leetcode] Longest Consecutive Sequence 最长连续数列

摘要：集合法复杂度时间空间思路将所有数都加入集合中，然后再遍历这些数，因为我们能的判断某个数是否在集合中，所以我们可以一个个向上或者向下检查。时间复杂度仍是，因为我们不会检查不存在于数组的数，而存在于数组的数也只会检查一次。 Longest Consecutive Sequence Given an unsorted array of integers, find the length o...

lei___ 2019-08-14 12:38 评论0 收藏0
128. Longest Consecutive Sequence-从数组中寻找最长的连续数字

摘要：描述例子要求分析从未排序的数组中寻找最长的连续的数字，必然要循环一遍所有的数字，因为连续，所以以出来的数字为基准，向左右扩散，直到没有连续的，利用了和的特性。描述： Given an unsorted array of integers, find the length of the longest consecutive elements sequence. 例子： Given ...

Pandaaa 2019-07-30 16:09 评论0 收藏0