Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.
-------------------------------------------- In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2hnodes inclusive at the last level h.
O(logN * logN)，遇到perfect tree, 直接计算并返回，反之继续数儿子们
看了答案
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
int left = 0, right = 0;
TreeNode *leftItr = root, *rightItr = root;
while (leftItr != NULL) {
left++;
leftItr = leftItr->left;
}
while (rightItr != NULL) {
right++;
rightItr = rightItr->right;
}
if (left == right) return pow(2,left) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
iterative
检查右子树是不是perfect tree，如果是，则缺口在左子树，此时加上右边的个数。
如果不是，则缺口在右子树，此时加上左边的个数
此题关键在于对高度的判断，然后对树的分解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int getHeight(TreeNode *root) {
int height = 0;
while (root != NULL) {
height++;
root = root->left;
}
return height;
}
int countNodes(TreeNode* root) {
int height = getHeight(root);
int count = 0;
while (root != NULL) {
if (getHeight(root->right) == height - 1) {
count += 1 << height - 1;
root = root->right;
}else {
count += 1 << height - 2;
root = root->left;
}
height--;
}
return count;
}
};
Rectangle Area
Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Assume that the total area is never beyond the maximum possible value of int.
看了答案
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
if (D < F || H < B || G < A || C < E) {
return (H - F) * (G - E) + (C - A) * (D - B);
}
int right = min(D,H) - max(B,F);
int top = min(C,G) - max(E,A);
return (D - B) * (C - A) + (H - F) * (G - E) - right * top;
}
};
Basic Calculator
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open
( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2 " 2-1 + 2 " = 3 "(1+(4+5+2)-3)+(6+8)" = 23---------------------------------------------------------------------
看了答案，用初始化 sign = 1来处理符号，能解决特殊情况.
对()的处理
class Solution {
public:
int calculate(string s) {
stack<int> st;
int sign = 1;
int rt = 0;
int num = 0;
for (int i = 0; i < s.length(); i++) {
if (isdigit(s[i])) {
num = num * 10 + s[i] - '0';
}else if (s[i] == '+') {
rt += sign * num;
sign = 1;
num = 0;
}else if (s[i] == '-') {
rt += sign * num;
sign = -1;
num = 0;
}else if (s[i] == '(') {
st.push(rt);
st.push(sign);
sign = 1;
rt = 0;
}else if (s[i] == ')') {
rt += num * sign;
sign = st.top();
st.pop();
rt = sign * rt + st.top();
st.pop();
num = 0;
}
}
if (num != 0) {
return rt + sign * num;
}
return rt;
}
};
Java, updated on Aug-16th-2018.
整体思路类似，只不过遇到数字做加减。上面c＋＋的算法是遇到符号做加减。
class Solution {
public int calculate(String s) {
Stack<Integer> st = new Stack<>();
int i = 0;
int eval = 0;
int sign = 1;
while (i < s.length()) {
char c = s.charAt(i);
if (c == '(') {
st.push(eval);
st.push(sign);
eval = 0;
sign = 1;
}else if (c == ')') {
sign = st.pop();
eval = st.pop() + eval * sign;
}else if (Character.isDigit(c)) {
String cur = "";
while (i < s.length() && Character.isDigit(s.charAt(i))) {
cur += s.charAt(i);
i++;
}
i--;
eval += sign * Integer.parseInt(cur);
}else if (c == '-') {
sign = -1;
}else if (c == '+') {
sign = 1;
}
i++;
}
return eval;
}
}
Implement Stack using Queues
Implement the following operations of a stack using queues.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- empty() -- Return whether the stack is empty.
- You must use only standard operations of a queue -- which means only
push to back,peek/pop from front,size, andis emptyoperations are valid. - Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
- You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
用queue的大小来控制倒腾，只用一个queue，而不是两个
class Stack {
public:
// Push element x onto stack.
void push(int x) {
topElem = x;
q.push(x);
}
// Removes the element on top of the stack.
void pop() {
for (int i = 0; i < q.size() - 1; i++) {
topElem = q.front();
q.push(q.front());
q.pop();
}
q.pop();
}
// Get the top element.
int top() {
return topElem;
}
// Return whether the stack is empty.
bool empty() {
return q.empty();
}
private:
queue<int> q;
int topElem;
};
Invert Binary Tree
Invert a binary tree.
4 / \ 2 7 / \ / \ 1 3 6 9to
4 / \ 7 2 / \ / \ 9 6 3 1---------------------------------------------------
recursive
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return NULL;
TreeNode *temp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(temp);
return root;
}
};
iterative
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
TreeNode *node = que.front();
que.pop();
TreeNode *temp = node->left;
node->left = node->right;
node->right = temp;
if (node->left != NULL) {
que.push(node->left);
}
if (node->right != NULL) {
que.push(node->right);
}
}
return root;
}
};
No comments:
Post a Comment