[LeetCode] 549. Binary Tree Longest Consecutive Se

bingchen 发布于2019-08-19 11:11 / 509人阅读

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] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:
Input:

    1
   / 
  2   3

Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].
Example 2:
Input:

    2
   / 
  1   3

Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].
Note: All the values of tree nodes are in the range of [-1e7, 1e7].

Solution

class Solution {
    private int maxLen = 0;
    public int longestConsecutive(TreeNode root) {
        //use recursion for tree 
        //should maintain two variables: increasing/decreasing sequence lengths
        helper(root);
        return maxLen;
    }
    private int[] helper(TreeNode root) {
        //terminate condition
        if (root == null) return new int[]{0, 0};
        
        //do recursion
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        
        //update increasing/decreasing sequence lengths: inc/dec
        int inc = 1, dec = 1;
        if (root.left != null) {
            if (root.left.val == root.val-1) inc = left[0]+1;
            if (root.left.val == root.val+1) dec = left[1]+1;
        }
        if (root.right != null) {
            if (root.right.val == root.val-1) inc = Math.max(inc, right[0]+1);
            if (root.right.val == root.val+1) dec = Math.max(dec, right[1]+1);
        }
        
        //update max length: maxLen
        maxLen = Math.max(maxLen, inc+dec-1);
        
        //pass in inc/dec into higher level recursion
        return new int[]{inc, dec};
    }
}

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/77162.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
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 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0