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}; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/77162.html
摘要:遞歸法復雜度時間空間思路因為要找最長的連續路徑,我們在遍歷樹的時候需要兩個信息,一是目前連起來的路徑有多長,二是目前路徑的上一個節點的值。代碼判斷當前是否連續返回當前長度,左子樹長度,和右子樹長度中較大的那個 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...
摘要:題目鏈接這一個類型的題都一樣用,分治的思想。兩種方式一種用,另一種直接把的長度作為返回值,思路都一樣。也可以解,用或者來做,但是本質都是。用用返回值在當前層處理分別處理左右節點,這樣不用傳上一次的值,注意這樣初始的就是了 Binary Tree Longest Consecutive Sequence 題目鏈接:https://leetcode.com/problems... 這一個類...
摘要:題目解答分治,一種不帶返回值,但需要用全局變量,一種帶返回值,不用全局變量有全局變量 題目: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...
摘要:在線網站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目,語言 JavaScript。 在線網站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...
摘要:月下半旬攻略道題,目前已攻略題。目前簡單難度攻略已經到題,所以后面會調整自己,在刷算法與數據結構的同時,攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區別...
閱讀 2885·2021-10-26 09:49
閱讀 3221·2021-10-14 09:42
閱讀 2042·2021-09-13 10:31
閱讀 2580·2019-08-30 11:13
閱讀 2962·2019-08-29 16:31
閱讀 1068·2019-08-29 13:58
閱讀 1859·2019-08-29 12:12
閱讀 3556·2019-08-26 13:48