298. Binary Tree Longest Consecutive Sequence

荆兆峰发布于2019-08-14 14:15 / 2991人阅读

摘要：题目解答分治，一种不带返回值，但需要用全局变量，一种带返回值，不用全局变量有全局变量

题目：
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,

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

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

解答：
分治，一种不带返回值，但需要用全局变量，一种带返回值，不用全局变量：
1.

//有全局变量
    private int max = 0;
    
    public void Helper(TreeNode root, int target, int count) {
        if (root == null) return;
        if (root.val == target) {
            count++;
        } else {
            count = 1;
        }
        max = Math.max(max, count);
        Helper(root.left, root.val + 1, count);
        Helper(root.right, root.val + 1, count);
    }
    
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        Helper(root, root.val + 1, 1);
        return max;
    }

public int Helper(TreeNode root, int target, int count) {
    if (root == null) return 1;
    count = root.val == target ? count + 1 : 1;
    int left = Helper(root.left, root.val + 1, count);
    int right = Helper(root.right, root.val + 1, count);
    
    return Math.max(Math.max(left, right), count);
}

public int longestConsecutive(TreeNode root) {
    if (root == null) return 0;
    return Math.max(Helper(root.left, root.val + 1, 1), Helper(root.right, root.val + 1, 1));
}

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/64903.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
Binary Tree Longest Consecutive Sequence

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

svtter 2019-08-14 17:19 评论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