資訊專欄INFORMATION COLUMN
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].
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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77162.html
摘要：遞歸法復(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 Given a binary tree, find the length of the lon...
摘要：題目鏈接這一個(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...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...
閱讀 2895·2021-10-26 09:49
閱讀 3230·2021-10-14 09:42
閱讀 2056·2021-09-13 10:31
閱讀 2599·2019-08-30 11:13
閱讀 2971·2019-08-29 16:31
閱讀 1086·2019-08-29 13:58
閱讀 1869·2019-08-29 12:12
閱讀 3595·2019-08-26 13:48
