- 问题**
给定一个有n个节点的二叉树,你需要找出树中最长幻灯片的长度。
滑动是从一个节点到另一个节点的路径,其中可以仅通过遍历左子节点或右子节点从另一个节点到达一个节点。
- 示例-**
设两个节点为2和10,从2开始,只遍历右子节点,就可以到达10。2-〉5-〉8-〉10。
另一个幻灯片是1到4。从1开始,只遍历左边的子节点,我们可以到达4。1-〉2-〉4。
并且1到5不是滑动,因为仅通过遍历左子节点或右子节点不能从1到达5。
幻灯片的长度等于幻灯片中的边数。例如,在2-〉5-〉8-〉10中有3条边,因此幻灯片从2到10的长度为3。
- 输入格式**
第一行包含整数n-节点数目。第二行包含n个以空格分隔的整数-节点的值。接下来的n行包含3个以空格分隔的整数i、l、r,分别将第i个节点的左子节点和右子节点描述为l和r。最后一行包含您需要寻找其镜像值的目的值。
- 输出格式**
输出最长幻灯片的长度。如果没有幻灯片,则打印0。
- 样品输入1**
10 21 46 34 15 23 35 65 7 72 54 1 2 3 2 4 5 3 6 -1 4 -1 -1 5 7 8 6 -1 -1 7 -1 -1 8 9
- 样品输出1**3
"这就是我的解决方案"
/*
Definition of TreeNode
class TreeNode {
public long val;
public TreeNode left;
public TreeNode right;
public TreeNode (long x) {
val = x;
left = null;
right = null;
}
}
*/
class Solution {
int max = 0;
public int longestSlideInTree(TreeNode root) {
helper(root);
return max;
}
private int helper(TreeNode root) {
if(root == null) {
return 0;
}
int res = 1;
int left = helper(root.left);
int right = helper(root.right);
if(left != 0 && root.left.val == root.val) {
res = Math.max(res, left + 1);
}
if(right != 0 && root.right.val == root.val) {
res = Math.max(res, right + 1);
}
max = Math.max(max, res);
return Math.max(res, 1);
}
}
错误显示预期输出为3,而我得到的输出为1
1条答案
按热度按时间dtcbnfnu1#
你可以试试这样的方法:
更新:
更新了helper函数,以遍历当前节点及其一个子节点。采用了遍历两个子节点的路径。