Created
May 4, 2017 20:28
-
-
Save thanlau/34bd056dd0b1662d5fd483e157a27dfb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
我的问题:一开始我不会多叉树如何表示其子节点 | |
list<TreeNode> children; root.children用来表示根的所有子节点 | |
for (MultiTreeNode child : root.children)用来表示遍历root的所有子树 | |
/** | |
* Definition for a multi tree node. | |
* public class MultiTreeNode { | |
* int val; | |
* List<TreeNode> children; | |
* MultiTreeNode(int x) { val = x; } | |
* } | |
*/ | |
public class Solution { | |
class ResultType{ | |
int maxLength, maxUp, maxDown; | |
public ResultType(int maxLength, int maxUp, int maxDown){ | |
this.maxLength = maxLength; | |
this.maxUp = maxUp; | |
this.maxDown = maxDown; | |
} | |
} | |
public int longestConsecutive3(MultiTreeNode root) { | |
// Write your code here | |
/**思路 | |
* 和Binary Tree Longest Consecutive Sequence II一样的做法。 | |
* II只要check一下left和right。 | |
* 这题因为有多个子节点,所以要用一个循环来check所有。*/ | |
if(root == null){ | |
return 0; | |
} | |
ResultType result = helper(root); | |
return result.maxLength; | |
} | |
private ResultType helper(MultiTreeNode root){ | |
if(root == null){ | |
return new ResultType(0,0,0); | |
} | |
int up = 0; | |
int down = 0; | |
int maxlength = 0; | |
//for循环check所有子树 | |
for(MultiTreeNode child : root.children){ | |
就和ii中 left = helper(root.left)一样, | |
都要递归算出得到了以root孩子为根的子树,最大连续上升是多少,最大连续下降是多少 | |
ResultType childresult = helper(child); | |
if(child.val + 1 == root.val){ | |
up = Math.max(childresult.maxUp + 1, up); | |
} | |
if(child.val - 1 == root.val){ | |
down = Math.max(childresult.maxDown + 1, down); | |
} | |
maxlength = Math.max(childresult.maxLength, maxlength); | |
} | |
maxlength = Math.max(maxlength,down + up + 1); | |
return new ResultType(maxlength,up,down); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment