H***e
发帖数: 476 | 1 第二题，
用往上面反值的方法， 左右子树传值给parent node. 总复杂度为O(n).
inside a class:
BSTNode maxsumNode = null;
int maxValue = Integer.MIN_VALUE;
public void findMaxSumSubtree(BSTNode node, MutableInt sum) {
// base cases:
if (node == null) {
sum.setValue(0);
return;
}
// normal cases:
MutableInt leftSum = new MutableInt();
MutableInt rightSum = new MutableInt();
findMaxSumSubtree(node.left, leftSum);
findMaxSumSubtree... 阅读全帖 |
|
e****e
发帖数: 418 | 2 DFS approach. My code is lousy, the point is to show the DFS approach.
Thanks.
public int[] dFS(TreeNode root ) {
int depth = depth( root );
int[] r = new int[depth];
boolean[] m = new boolean[depth];
if ( root == null )
return r;
dFSCore( root, new MutableInt(0), r, m );
return r;
}
private void dFSCore( TreeNode node, MutableInt level, int[] r, boolean[
] m ) {
if ( node == null )
... 阅读全帖 |
|
e****e
发帖数: 418 | 3 Assume there is only one value got duplicated.
global variable: int count = 0;
void inorderDFS(Node n, MutableInt prev) {
if ( node == null )
return;
inorderDFS( node.left, prev );
if ( n.val == prev.val )
count++;
pre.val = node.val;
inorderDFS( node.right, prev );
}
invoke: inorderDFS( root, new MutableInt() );
return: count
class MutableInt {
int val;
} |
|
