[Leetcode] Binary Tree Longest Consecutive Sequenc

xi4oh4o 发布于2019-08-14 16:16 / 2225人阅读

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

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

递归法 复杂度

时间O(n) 空间O(h)

思路

因为要找最长的连续路径，我们在遍历树的时候需要两个信息，一是目前连起来的路径有多长，二是目前路径的上一个节点的值。我们通过递归把这些信息代入，然后通过返回值返回一个最大的就行了。这种需要遍历二叉树，然后又需要之前信息的题目思路都差不多，比如Maximum Depth of Binary Tree和Binary Tree Maximum Path Sum。

代码

public class Solution {
    public int longestConsecutive(TreeNode root) {
        if(root == null){
            return 0;
        }
        return findLongest(root, 0, root.val - 1);
    }
    
    private int findLongest(TreeNode root, int length, int preVal){
        if(root == null){
            return length;
        }
        // 判断当前是否连续
        int currLen = preVal + 1 == root.val ? length + 1 : 1;
        // 返回当前长度，左子树长度，和右子树长度中较大的那个
        return Math.max(currLen, Math.max(findLongest(root.left, currLen, root.val), findLongest(root.right, currLen, root.val)));  
    }
}

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

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

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

[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
Binary Tree Longest Consecutive Sequence

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

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

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论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