-
第 23 楼 / webdriver
- 时间: 2014-9-27 01:40S算法问题: Binary Tree Maximum Path Sum
问题描述:
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6. -
-
- 时间: 2014-9-27 01:41算法问题推荐解法来了...
Recursion...
解法（Java）
代码:
public class BinaryTreeMaximumPathSum {
public int maxPathSum(TreeNode root) {
if (root == null)
return 0;
int[] max = new int[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
return max[0];
}
private int maxPathSum(TreeNode root, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
return root.val;
} else if (root.left != null && root.right == null) {
int left = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(
root.val, max[0]);
return left > 0 ? left + root.val : root.val;
} else if (root.left == null && root.right != null) {
int right = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(
root.val, max[0]);
return right > 0 ? right + root.val : root.val;
} else {
int left = maxPathSum(root.left, max);
int right = maxPathSum(root.right, max);
int tmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
return Math.max(Math.max(left, right), 0) + root.val;
}
}
} -
-
- 时间: 2014-9-27 01:42
-
- 时间: 2014-9-27 01:42算法问题推荐解法来了...
1. Iterative way (stack). Time: O(n), Space: O(n).
2. Recursive solution. Time: O(n), Space: O(n).
3. Threaded tree (Morris). Time: O(n), Space: O(1).
You may refer to my blog for more detailed explanations:
www.cnblogs.com/AnnieK...ersal.html
解法（Java）
代码:
import java.util.ArrayList;
import java.util.Stack;
public class BinaryTreePostorderTraversal {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (root == null)
return ret;
Stack<TreeNode> st = new Stack<TreeNode>();
TreeNode p = root.right;
ret.add(root.val);
st.add(root);
while (!st.isEmpty()) {
while (p != null) {
ret.add(p.val);
st.add(p);
p = p.right;
}
TreeNode node = st.pop();
p = node.left;
if (p != null) {
ret.add(p.val);
st.add(p);
p = p.right;
}
}
int i = 0;
int j = ret.size() - 1;
while(i < j) {
int tmp = ret.get(i);
ret.set(i, ret.get(j));
ret.set(j, tmp);
i++;
j--;
}
return ret;
}
}
-
- 时间: 2014-9-27 01:43
-
- 时间: 2014-9-27 01:44S算法问题: Binary Tree Zigzag Level Order Traversal
问题描述:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left
to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
] -
- 时间: 2014-9-27 01:45
-
- 时间: 2014-9-27 01:46S算法问题: Candy
问题描述:
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give? -
- 时间: 2014-9-27 01:46算法问题推荐解法来了...
You may refer to github.com/AnnieKim/IT...%9E%9C.cpp
1. traverse only once with O(1) space. 2. O(n) space.
解法（Java）
代码:
public class Candy {
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
candy[0] = 1;
for (int i = 1; i < ratings.length; i++) {
candy[i] = ratings[i] > ratings[i - 1] ? candy[i - 1] + 1 : 1;
}
int totalCandy = candy[ratings.length - 1];
for (int i = ratings.length - 2; i >= 0; i--) {
candy[i] = (ratings[i] > ratings[i + 1] && candy[i + 1] + 1 > candy[i]) ? candy[i + 1] + 1 : candy[i];
totalCandy += candy[i];
}
return totalCandy;
}
} -
- 时间: 2014-9-27 01:47
Leetcode Hacking Practice -- Solution in Java Part 1
