g**e
发帖数: 6127 | 1 https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/ 变种
求binary tree两个leaf之间path的最大值, 起点可以从任何一个leaf node. e.g:
3
/ \
1 4
/ / \
1 6 5
return 64311
1
/
1
/ \
4 3
return 413
int getMaxNum(Node root) {} |
l*****a
发帖数: 14598 | 2 大牛刷题不够啊
https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
hehe
【在 g**e 的大作中提到】
: https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/ 变种
: 求binary tree两个leaf之间path的最大值, 起点可以从任何一个leaf node. e.g:
: 3
: / \
: 1 4
: / / \
: 1 6 5
: return 64311
: 1
: /
|
g**e
发帖数: 6127 | |
l*****a
发帖数: 14598 | 4 oh
两个leaf...
【在 g**e 的大作中提到】
: 大牛再仔细看看，跟我说的是一样吗。那个太容易了
|
B********t
发帖数: 147 | 5 恩 难多了
感觉要要记录path 之前那题只要算出和就行。 |
g**e
发帖数: 6127 | 6 不是求和，是两个leaf之间的path组成的数字，可以从左往右或从右往左
【在 l*****a 的大作中提到】
: oh
: 两个leaf...
|
A*****i
发帖数: 3587 | |
w*******s
发帖数: 138 | 8 遍历树中所有最长路径即可，最长路径有O(n)方法
【在 g**e 的大作中提到】
: https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/ 变种
: 求binary tree两个leaf之间path的最大值, 起点可以从任何一个leaf node. e.g:
: 3
: / \
: 1 4
: / / \
: 1 6 5
: return 64311
: 1
: /
|
d**e
发帖数: 6098 | 9 有点像G电面我的题目,是不是跟最长任意两点路径差不多?
【在 g**e 的大作中提到】
: https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/ 变种
: 求binary tree两个leaf之间path的最大值, 起点可以从任何一个leaf node. e.g:
: 3
: / \
: 1 4
: / / \
: 1 6 5
: return 64311
: 1
: /
|
g**e
发帖数: 6127 | 10 类似，更复杂一点。路径最长数字不一定最大。而且路径正反数字也有变化
【在 d**e 的大作中提到】
: 有点像G电面我的题目,是不是跟最长任意两点路径差不多?
|
|
|
c********6
发帖数: 33 | 11 您看看我这个行吗，只用了您给的两个数据，
static int result = Integer.MIN_VALUE;
static int getMaxNum(TreeNode root)
{
if(root == null) return 0;
pathMax(root);
return result;
}
static int pathMax(TreeNode root)
{
if(root == null) return 0;
if(root.left == null) return pathMax(root.right) * 10 + root.val;
if(root.right == null) return pathMax(root.left) * 10 + root.val;
int leftMax = pathMax(root.left);
int rightMax = pathMax(root.right);
int max = Math.max(leftMax, rightMax);
int min = Math.min(leftMax, rightMax);
double digit = String.valueOf(min).length();
int head = max * 10 + root.val;
result = Math.max(result, head * (int)Math.pow(10.0, digit) + min);
return max * 10 + root.val;
} |
s*i
发帖数: 5025 | 12 牛！这个题有点意思！
还要考虑到最长路径中 0 到 0 的情况。 |
z**a
发帖数: 69 | 13 诉我眼拙，没看出这题哪有陷阱。对每个节点找出其左右子树（lv, rv)的最大值，计
算，update现有的最大值。返回lv*10+curr->val 或者rv+curr->val。自底向上，这个
方法有什么问题吗？ |
J*****a
发帖数: 46 | 14 是说最长的 path 的吗？还是类似的 dp 就好了
而且可以不说是两个 leaf 因为最长 path 必定是两个 leaf 之间 |
e*******s
发帖数: 1979 | 15 找least common parent就得用union find吧 然后求个min
【在 g**e 的大作中提到】
: https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/ 变种
: 求binary tree两个leaf之间path的最大值, 起点可以从任何一个leaf node. e.g:
: 3
: / \
: 1 4
: / / \
: 1 6 5
: return 64311
: 1
: /
|
h*******e
发帖数: 1377 | 16 对于每个root 返回两个值，到本点最大长度 中leaf到本点最大值和本点到leaf 最大值
，之后把左右两个子树 返回的pair 和 本点val 处理一下某种求和 然后把这两个值
和全局 maxval 比较 最后返回全局 maxval 如果没说明 要注意处理 溢出情况~~~ |
y**********a
发帖数: 824 | 17 有问题。
最后的 min 是从叶子到根的值。应该是从根到叶子才行。
【在 c********6 的大作中提到】
: 您看看我这个行吗，只用了您给的两个数据，
: static int result = Integer.MIN_VALUE;
: static int getMaxNum(TreeNode root)
: {
: if(root == null) return 0;
: pathMax(root);
: return result;
: }
:
: static int pathMax(TreeNode root)
|
