資訊專欄INFORMATION COLUMN
摘要：題目鏈接這一個(gè)類型的題都一樣用，分治的思想。兩種方式一種用，另一種直接把的長(zhǎng)度作為返回值，思路都一樣。也可以解，用或者來做，但是本質(zhì)都是。用用返回值在當(dāng)前層處理分別處理左右節(jié)點(diǎn)，這樣不用傳上一次的值，注意這樣初始的就是了
Binary Tree Longest Consecutive Sequence
題目鏈接：https://leetcode.com/problems...
這一個(gè)類型的題都一樣用dfs，分治的思想。兩種方式：一種用global variable，另一種直接把sequence的長(zhǎng)度作為返回值，思路都一樣。也可以直接在當(dāng)前層對(duì)左右節(jié)點(diǎn)分別處理，本質(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.在當(dāng)前層處理分別處理左右節(jié)點(diǎn)，這樣不用傳上一次的值，注意這樣初始的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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/66560.html
摘要：遞歸法復(fù)雜度時(shí)間空間思路因?yàn)橐易铋L(zhǎng)的連續(xù)路徑，我們?cè)诒闅v樹的時(shí)候需要兩個(gè)信息，一是目前連起來的路徑有多長(zhǎng)，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長(zhǎng)度，左子樹長(zhǎng)度，和右子樹長(zhǎng)度中較大的那個(gè) 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] ...
摘要：集合法復(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...
摘要：描述例子要求分析從未排序的數(shù)組中尋找最長(zhǎng)的連續(xù)的數(shù)字，必然要循環(huán)一遍所有的數(shù)字，因?yàn)檫B續(xù)，所以以出來的數(shù)字為基準(zhǔn)，向左右擴(kuò)散，直到?jīng)]有連續(xù)的，利用了和的特性。 描述： Given an unsorted array of integers, find the length of the longest consecutive elements sequence. 例子： Given ...
閱讀 3694·2021-11-11 10:58
閱讀 2476·2021-09-22 15:43
閱讀 2869·2019-08-30 15:44
閱讀 2188·2019-08-30 13:08
閱讀 1821·2019-08-29 17:28
閱讀 884·2019-08-29 10:54
閱讀 675·2019-08-26 11:46
閱讀 3507·2019-08-26 11:43
