[Leetcode] Binary Tree Longest Consecutive Sequenc

xi4oh4o 發布于2019-08-14 16:16 / 2233人閱讀

摘要：遞歸法復雜度時間空間思路因為要找最長的連續路徑，我們在遍歷樹的時候需要兩個信息，一是目前連起來的路徑有多長，二是目前路徑的上一個節點的值。代碼判斷當前是否連續返回當前長度，左子樹長度，和右子樹長度中較大的那個

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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