資訊專欄INFORMATION COLUMN
摘要：題目鏈接這一個類型的題都一樣用，分治的思想。兩種方式一種用，另一種直接把的長度作為返回值，思路都一樣。也可以解，用或者來做，但是本質(zhì)都是。用用返回值在當前層處理分別處理左右節(jié)點，這樣不用傳上一次的值，注意這樣初始的就是了
Binary Tree Longest Consecutive Sequence
題目鏈接：https://leetcode.com/problems...
這一個類型的題都一樣用dfs，分治的思想。兩種方式：一種用global variable，另一種直接把sequence的長度作為返回值，思路都一樣。也可以直接在當前層對左右節(jié)點分別處理，本質(zhì)和前面一樣的。iteration也可以解，用stack或者queue來做，但是本質(zhì)都是dfs。
1.用global variable
public int longestConsecutive(TreeNode root) {
/* dfs
* arguments: curNode, previous value, length
* 2 chooses: 1. curNode.val >= previous_value => length + 1
* 2. curNode.val < previous_value => length = 1
* update length each recursion: use a global variable
*/
if(root == null) return 0;
dfs(root, root.val - 1, 0);
return global;
}
int global = 0;
private void dfs(TreeNode curNode, int previous_value, int len) {
// update global length
global = Math.max(global, len);
// base case
if(curNode == null) {
return;
}
if(curNode.val - previous_value == 1) len++;
else len = 1;
dfs(curNode.left, curNode.val, len);
dfs(curNode.right, curNode.val, len);
}
2.用返回值
public int longestConsecutive(TreeNode root) {
/* dfs
* arguments: curNode, previous value, length
* 2 chooses: 1. curNode.val >= previous_value => length + 1
* 2. curNode.val < previous_value => length = 1
* update length each recursion: return the max length
*/
if(root == null) return 0;
return dfs(root, root.val - 1, 0);
}
private int dfs(TreeNode curNode, int previous_value, int len) {
// base case
if(curNode == null) {
return len;
}
if(curNode.val - previous_value == 1) len++;
else len = 1;
return Math.max(len, Math.max(dfs(curNode.left, curNode.val, len), dfs(curNode.right, curNode.val, len)));
}
3.在當前層處理分別處理左右節(jié)點，這樣不用傳上一次的值，注意這樣初始的len就是1了：
public int longestConsecutive(TreeNode root) {
if(root == null) return 0;
dfs(root, 1);
return global;
}
int global = 0;
private void dfs(TreeNode curNode, int len) {
global = Math.max(global, len);
if(curNode.left != null) {
if(curNode.val + 1 == curNode.left.val) dfs(curNode.left, len+1);
else dfs(curNode.left, 1);
}
if(curNode.right != null) {
if(curNode.val + 1 == curNode.right.val) dfs(curNode.right, len+1);
else dfs(curNode.right, 1);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66560.html
摘要：遞歸法復雜度時間空間思路因為要找最長的連續(xù)路徑，我們在遍歷樹的時候需要兩個信息，一是目前連起來的路徑有多長，二是目前路徑的上一個節(jié)點的值。代碼判斷當前是否連續(xù)返回當前長度，左子樹長度，和右子樹長度中較大的那個 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...
摘要：題目解答分治，一種不帶返回值，但需要用全局變量，一種帶返回值，不用全局變量有全局變量 題目：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...
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] ...
摘要：集合法復雜度時間空間思路將所有數(shù)都加入集合中，然后再遍歷這些數(shù)，因為我們能的判斷某個數(shù)是否在集合中，所以我們可以一個個向上或者向下檢查。時間復雜度仍是，因為我們不會檢查不存在于數(shù)組的數(shù)，而存在于數(shù)組的數(shù)也只會檢查一次。 Longest Consecutive Sequence Given an unsorted array of integers, find the length o...
摘要：描述例子要求分析從未排序的數(shù)組中尋找最長的連續(xù)的數(shù)字，必然要循環(huán)一遍所有的數(shù)字，因為連續(xù)，所以以出來的數(shù)字為基準，向左右擴散，直到?jīng)]有連續(xù)的，利用了和的特性。 描述： Given an unsorted array of integers, find the length of the longest consecutive elements sequence. 例子： Given ...
閱讀 3710·2021-11-11 10:58
閱讀 2498·2021-09-22 15:43
閱讀 2880·2019-08-30 15:44
閱讀 2202·2019-08-30 13:08
閱讀 1834·2019-08-29 17:28
閱讀 898·2019-08-29 10:54
閱讀 687·2019-08-26 11:46
閱讀 3518·2019-08-26 11:43
