資訊專欄INFORMATION COLUMN
摘要：遞歸法復(fù)雜度時(shí)間空間思路因?yàn)橐易铋L(zhǎng)的連續(xù)路徑，我們?cè)诒闅v樹(shù)的時(shí)候需要兩個(gè)信息，一是目前連起來(lái)的路徑有多長(zhǎng)，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長(zhǎng)度，左子樹(shù)長(zhǎng)度，和右子樹(shù)長(zhǎng)度中較大的那個(gè)
Binary Tree Longest Consecutive Sequence
遞歸法 復(fù)雜度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 5Longest consecutive sequence path is 3-4-5, so return 3.
2 3 / 2 / 1Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
時(shí)間O(n) 空間O(h)
思路因?yàn)橐易铋L(zhǎng)的連續(xù)路徑，我們?cè)诒闅v樹(shù)的時(shí)候需要兩個(gè)信息，一是目前連起來(lái)的路徑有多長(zhǎng)，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。我們通過(guò)遞歸把這些信息代入，然后通過(guò)返回值返回一個(gè)最大的就行了。這種需要遍歷二叉樹(shù)，然后又需要之前信息的題目思路都差不多，比如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;
}
// 判斷當(dāng)前是否連續(xù)
int currLen = preVal + 1 == root.val ? length + 1 : 1;
// 返回當(dāng)前長(zhǎng)度，左子樹(shù)長(zhǎng)度，和右子樹(shù)長(zhǎng)度中較大的那個(gè)
return Math.max(currLen, Math.max(findLongest(root.left, currLen, root.val), findLongest(root.right, currLen, root.val)));
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66176.html
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] ...
摘要：題目鏈接這一個(gè)類型的題都一樣用，分治的思想。兩種方式一種用，另一種直接把的長(zhǎng)度作為返回值，思路都一樣。也可以解，用或者來(lái)做，但是本質(zhì)都是。用用返回值在當(dāng)前層處理分別處理左右節(jié)點(diǎn)，這樣不用傳上一次的值，注意這樣初始的就是了 Binary Tree Longest Consecutive Sequence 題目鏈接：https://leetcode.com/problems... 這一個(gè)類...
摘要：題目解答分治，一種不帶返回值，但需要用全局變量，一種帶返回值，不用全局變量有全局變量 題目：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...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：集合法復(fù)雜度時(shí)間空間思路將所有數(shù)都加入集合中，然后再遍歷這些數(shù)，因?yàn)槲覀兡艿呐袛嗄硞€(gè)數(shù)是否在集合中，所以我們可以一個(gè)個(gè)向上或者向下檢查。時(shí)間復(fù)雜度仍是，因?yàn)槲覀儾粫?huì)檢查不存在于數(shù)組的數(shù)，而存在于數(shù)組的數(shù)也只會(huì)檢查一次。 Longest Consecutive Sequence Given an unsorted array of integers, find the length o...
閱讀 609·2023-04-25 16:00
閱讀 1666·2019-08-26 13:54
閱讀 2526·2019-08-26 13:47
閱讀 3493·2019-08-26 13:39
閱讀 1087·2019-08-26 13:37
閱讀 2787·2019-08-26 10:21
閱讀 3563·2019-08-23 18:19
閱讀 1626·2019-08-23 18:02
