国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LeetCode] 549. Binary Tree Longest Consecutive Se

bingchen / 518人閱讀

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/77162.html

相關(guān)文章

  • [Leetcode] Binary Tree Longest Consecutive Sequenc

    摘要：遞歸法復(fù)雜度時間空間思路因?yàn)橐易铋L的連續(xù)路徑，我們在遍歷樹的時候需要兩個信息，一是目前連起來的路徑有多長，二是目前路徑的上一個節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長度，左子樹長度，和右子樹長度中較大的那個 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

    xi4oh4o 評論0 收藏0

  • Binary Tree Longest Consecutive Sequence

    摘要：題目鏈接這一個類型的題都一樣用，分治的思想。兩種方式一種用，另一種直接把的長度作為返回值，思路都一樣。也可以解，用或者來做，但是本質(zhì)都是。用用返回值在當(dāng)前層處理分別處理左右節(jié)點(diǎn)，這樣不用傳上一次的值，注意這樣初始的就是了 Binary Tree Longest Consecutive Sequence 題目鏈接：https://leetcode.com/problems... 這一個類...

    svtter 評論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...

    荊兆峰 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<