分别计算二叉树奇数层和偶数层的和-- 一道amazon面试题
You are given a function calcDifference which takes in the root pointer of a binary tree as it's input. Complete the function to return the sum of values of nodes at odd height - sum of values of node at even height. Consider the root node is at height 1. The structure is already declared, you can just start initializing nodes:
struct node {
struct node *left,*right;
int val;

}

首先，要道歉哈，题目本意是要求计算奇数层总和和偶数层总合的差值，但是我给改成分别计算它们的和了。但是也可以尝试 一下计算它们和的差值，之后会给出答案。

显然这个题目要用层次遍历来解决，如果有先根或者中根什么的，应该不能做到计算奇数和偶数层的和。用了c++中的两个queue，每个一个queue分别记录一层的节点，然后在进行交换，m_queue2起到辅助的作用，要不然普通的层次遍历中只是用一个queue不是能够很好的完成任务。因为是层次遍历，所以时间复杂度应该在O（n）。下面给出代码：

#include<iostream>#include<queue>using namespace std;typedef struct node{int data;struct node *left, *right;}BTNode, *Tree;#define NIL 0int a[] = {1, 2, 4, 0, 0, 5, 0, 0, 3, 6, 0, 0, 7, 0, 0};static int i = 0;void pre_order_create(Tree &T) {int num = a[i++];if(num == NIL) {T = NULL;} else {T = (BTNode*)malloc(sizeof(BTNode));T->data = num;pre_order_create(T->left);pre_order_create(T->right);}}void calculate(Tree T, int *odd_sum, int *even_sum) {queue<BTNode*> *m_queue1 = new queue<BTNode*>();queue<BTNode*> *m_queue2 = new queue<BTNode*>();queue<BTNode*> *temp_queue;BTNode *temp;int level = 1;int *sum;m_queue1->push(T);while(!m_queue1->empty()) {if(level % 2 == 1) {sum = odd_sum;} else {sum = even_sum;}while(m_queue1->size() > 0) {temp = m_queue1->front();(*sum) += temp->data;if(temp->left) {m_queue2->push(temp->left);}if(temp->right) {m_queue2->push(temp->right);}m_queue1->pop();}level++;temp_queue = m_queue1;m_queue1 = m_queue2;m_queue2 = temp_queue;}}int cal_diff(Tree T) {int temp;if(T == NULL) {return 0;} else {temp = T->data - cal_diff(T->left) - cal_diff(T->right);}return temp;}void main() {Tree T = NULL;pre_order_create(T);int odd_sum = 0;int even_sum = 0;calculate(T, &odd_sum, &even_sum);cout << "odd_sum=" << odd_sum << ",even_sum=" << even_sum << endl;cout << "diff=" << cal_diff(T) << endl;getchar();}