---

二叉树结点结构体定义

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

1. 给定二叉树，返回其前序遍历

int *array;
int size;
//array + size = 顺序表，用全局变量来构建一个顺序表

void preorder(struct TreeNode *root){
    if(root != NULL){       //写成(!root)不可以
        array[size++] = root->val;
        preorder(root->left);
        preorder(root->right);
    }
} 
    
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    array = (int*)malloc(1000000*sizeof(int));
    size = 0;
    
    preorder(root);
    *returnSize = size;
    return array;
}

---

2. 相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL){
        return true;
    }
    if(p == NULL || q == NULL){
        return false;
    }
    return p->val == q->val 
        && isSameTree(p->left,q->left)
        && isSameTree(p->right,q->right);
}

---

3. 另一个树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。
s 的一个子树包括 s 的一个节点和这个节点的所有子孙。
s 也可以看做它自身的一棵子树。

bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
    if(s == NULL){
        return false;
    }
    
    //需要调用前面封装好的isSame函数进行操作，使用时要完善这部分代码
    if(isSame(s,t)) {
        return true;
    }
    if(isSubtree(s->left,t) == true){
        return true;
    }
    return isSubtree(s->right,t);      //也可以写成if语句，但是如果上面不满足，他就成为了决定性因素
}

---

4. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

int maxDepth(struct TreeNode* root) {
    if(root == NULL){
        return 0;
    }
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return left > right ? left+1 : right+1;
    //这个 1 是根节点的层数
}

---

5. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

bool isBalanced(struct TreeNode* root) {
    if(root == NULL){
        return true;
    }
    if(isBalanced(root->left) == false){
        return false;
    }
    if(isBalanced(root->right) == false){
        return false;
    }
    int left = maxDepth(root->left);		//调用最大深度接口
    int right = maxDepth(root->right);
    int diff = left - right; 
    
    if(diff < -1 || diff > 1){
        return false;
    }
    return  true;
}

---

6. 对称二叉树

【本题与第二题：判断是否为相同的树大同小异】

给定一个二叉树，检查它是否是镜像对称。的。

bool isMirror(Node *p,Node *q){
	if(p == NULL && q == NULL){
		return true;
	}
	if(p == NULL || q == NULL){
		return false;
	}
	return p->val == q->val
		&& isMirror(p->left,q->right);
		&& isMirror(p->right,q->left);
}

---

7. 二叉树遍历

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F###其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

示例：

• 输入：abc##de#g##f###
• 输出：c b e g d f a

typedef struct Node {
    int value;
    struct Node *next;
}  Node ;

Node *CreateTree(char preorder[],int size,int *used){
	if(size == 0){
		*used = 0;
		return NULL;
	}
	if(preorder[0] = '#'){
		*used = 1;	//用掉了一个井号
		return NULL;
	}
			
	Node *root = malloc(sizeof(Node));
	root>value = preorder[0];
	
	int leftUsed;
	root->left = CreateTree(preorder+1,size - 1,&leftUsed);
	
	int rightUsed;
	root->right = CreateTree(preorder+1-leftUsed,size-1-leftUsed,&rightUsed);

	*used = 1 + leftUsed + rightUsed;
	return root;
}