ajawaid191
BAN USERO(n)
int getHeight(Node root) {
if (root == null) {
return 0;
}
int height = 0;
for (int i = 0; i < root.children; i++) {
height = max(height, getHeight(root.children[i]));
}
return height + 1;
}
- ajawaid191 April 14, 2017Start from the right most node, that will remain as is, since it is the largest node. Then as you move back up, add the sum from the right side to the value, and send the sum to the left (since all the values on the left will be less than all on right).
void updateWithSum(Node root) {
updateWithSum(root, 0);
}
int updateWithSum(Node root, int sumSoFar) {
if (root == null) {
return sumSoFar;
}
root.value += updateWithSum(root.right, sumSoFar);
int sumFromLeft = updateWithSum(root.left, root.Value);
return sumFromLeft;
}
Using DFS:
bool isMirrored(Node root) {
Queue<int> mirrorQ;
isMirroredPush(root.left, mirrorQ);
return isMirrored(root.right, mirrorQ);
}
void isMirroredPush(Node root, Queue<int> mirrorQ) {
if (root == null) {
mirrorQ.enqueue(-1);
return;
}
mirrorQ.enqueue(root.value);
isMirroredPush(root.left, mirrorQ);
isMIrroredPush(root.right, mirrorQ);
}
bool isMirrored(Node root, Queue<int> mirrorQ) {
if (mirrorQ.size() == 0) {
return false;
}
int val = mirrorQ.dequeue();
if (root == null) {
return val == -1;
}
if (root.value != val) {
return false;
}
return isMirrored(root.right, mirrorQ) && isMirrored(root.left, mirrorQ);
}
Q3.
Node getCommonAncestor(Node root, Node n1, Node n2) {
bool fakeBool = false;
return getCommonAncestor(root, n1, n2, &fakebool, &fakebool);
}
Node getCommonAncestor(Node root, Node n1, Node n2, bool& isN1Found, bool& isN2Found) {
if (root == null) {
return null;
}
bool _isN1Found = false;
bool _isN2Found = false;
if (root == n1) {
_isN1Found = true;
isN1Found = true;
}
if (root == n2) {
_isN1Found = true;
isN2Found = true;
}
Node possibleResult = getCommonAncestor(root.left, n1, _isN1Found, _isN2Found);
if (possibleResult != null) {
return possibleResult;
}
if (_isN1Found) {
isN1Found = true;
}
if (_isN2Found) {
_isN2Found = true;
}
if (_isN1Found && _isN2Found) {
return root;
}
Node possibleResult = getCommonAncestor(root.right, n1, _isN1Found, _isN2Found);
if (possibleResult != null) {
return possibleResult;
}
if (_isN1Found) {
isN1Found = true;
}
if (_isN2Found) {
_isN2Found = true;
}
if (_isN1Found && _isN2Found) {
return root;
}
return null;
}
Q1.
Node getCommonAncestor(Node root, Node n1, Node n2) {
if (root == null) {
return null;
}
int largerValue = n1.value > n2.value ? n1.value : n2.value;
int smallerValue = n1.value > n2.value ? n1.value : n2.value;
if (root.value >= smallerValue && root.value <= largerValue) {
return root;
}
if (root.value > largerValue) {
return getCommonAncestor(root.left, n1, n2);
}
if (root.value < smallerValue) {
return getCommonAncestor(root.right, n1, n2);
}
}
- ajawaid191 April 13, 2017Q2.
Node getCommonAncestor(Node root, Node n1, Node n2) {
if (root == null) {
return null;
}
int largerValue = n1.value > n2.value ? n1.value : n2.value;
int smallerValue = n1.value > n2.value ? n1.value : n2.value;
if (root.value >= smallerValue && root.value <= largerValue) {
if (root.left.value == root.value) {
return getCommonAncestor(root.left, n1, n2);
} else {
return root;
}
}
if (root.value > largerValue) {
return getCommonAncestor(root.left, n1, n2);
}
if (root.value < smallerValue) {
return getCommonAncestor(root.right, n1, n2);
}
}
- ajawaid191 April 13, 2017Q1.
Node getCommonAncestor(Node root, Node n1, Node n2) {
if (root == null) {
return null;
}
int largerValue = n1.value > n2.value ? n1.value : n2.value;
int smallerValue = n1.value > n2.value ? n1.value : n2.value;
if (root.value >= smallerValue && root.value <= largerValue) {
return root;
}
if (root.value > largerValue) {
return getCommonAncestor(root.left, n1, n2);
}
if (root.value < smallerValue) {
return getCommonAncestor(root.right, n1, n2);
}
}
}
- ajawaid191 April 15, 2017