【数据结构】二叉树（OJ）

  如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。
  这道题的思路比较简单，就是记录根节点的值，然后进行遍历，如果遇到不同的值就返回false，如果遍历完之后，仍旧没有不同的值，就返回true。

bool isUnivalTree(struct TreeNode* root){
    if(NULL == root)
        return true;
    // 如果左右节点为空，则没有比较的必要了，因为不存在
    if(root->left && root->left->val != root->val)
        return false;
    if(root->right && root->right->val != root->val)
        return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

  给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
  这道题和上一道题的思路类似，两个树同步进行遍历，如果遇到不同的就返回false，遍历完之后仍旧没有相同值就返回true。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(NULL == p && NULL == q)
        return true;

    if(NULL == p || NULL == q)
        return false;

    if(p->val != q->val)
        return false;

    return isSameTree(p->left, q->left)
    && isSameTree(p->right, q->right);
}

  给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
  这道题需要基于上一道题来做，如果没有上一道题的铺垫，这道题的难度会再上一个系数。解题思路就是将每一个子树与subRoot进行比较，有相同的就返回true，否则就返回false。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(NULL == p && NULL == q)
        return true;

    if(NULL == p || NULL == q)
        return false;

    if(p->val != q->val)
        return false;

    return isSameTree(p->left, q->left)
    && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(NULL == root)
        return false;

    if(isSameTree(root, subRoot))
        return true;

    return isSubtree(root->left, subRoot)
    || isSubtree(root->right, subRoot);
}

  给你一个二叉树的根节点 root ， 检查它是否轴对称。
  本质还是判断两个树是否相同，不过是左子树与左子树比、右子树与右子树比，换成了左子树与右子树比、右子树与左子树比。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(NULL == p && NULL == q)
        return true;

    if(NULL == p || NULL == q)
        return false;

    if(p->val != q->val)
        return false;

    return isSameTree(p->left, q->right)
    && isSameTree(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root){
    return isSameTree(root->left, root->right);
}

  给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
  这道题的核心在于交换左右子树，实际上应该保留原二叉树的，但是我懒，就直接交换了。

struct TreeNode* invertTree(struct TreeNode* root){
    if(NULL == root)
        return NULL;

    invertTree(root->left);
    invertTree(root->right);
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node = root->left;
    root->left = root->right;
    root->right = node;

    return root;
}

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

#include <stdio.h>
#include <stdlib.h>
struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* rebulidTree(char* str, int* pi)
{
    if('#' == str[*pi])
    {
        (*pi)++;
        return NULL;
    }

    struct TreeNode* root  = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = str[(*pi)++];
    root->left = rebulidTree(str, pi);
    root->right = rebulidTree(str, pi);

    return root;
}

void InOrder(struct TreeNode* root)
{
    if(NULL == root)
        return;

    InOrder(root->left);
    printf("%c ", root->val);
    InOrder(root->right);
}
int main() {
    char str[100];
    scanf("%s", str);

    int i = 0;
    struct TreeNode* root = rebulidTree(str, &i);

    InOrder(root);

    return 0;
}

  给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
  实际上就是求二叉树的高度。

int maxDepth(struct TreeNode* root){
    if(NULL == root)
        return 0;

    int left = maxDepth(root->left);
    int right = maxDepth(root->right);

    return (left > right ? left : right) + 1;
}

  给你二叉树的根节点 root ，返回它节点值的前序遍历。

 int TreeSize(struct TreeNode* root)
 {
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
 }
 void preorder(struct TreeNode* root, int* a, int* pi)
 {
     if(NULL == root)
        return;

    a[(*pi)++] = root->val;
    preorder(root->left, a, pi);
    preorder(root->right, a, pi);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = TreeSize(root);
    int* a = (int*)malloc(*returnSize * sizeof(int));
    int i = 0;
    preorder(root, a, &i);

    return a;
}

  给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void InOrder(struct TreeNode* root, int* a, int* pi)
{
    if(NULL == root)
        return;

    InOrder(root->left, a, pi);
    a[(*pi)++] = root->val;
    InOrder(root->right, a, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = TreeSize(root);
    int* a = (int*)malloc(*returnSize * sizeof(int));
    int i = 0;
    InOrder(root, a, &i);

    return a;
}

  给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void postOrder(struct TreeNode* root, int* a, int* pi)
{
    if(NULL == root)
        return;

    postOrder(root->left, a, pi);
    postOrder(root->right, a, pi);
    a[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = TreeSize(root);
    int* a = (int*)malloc(*returnSize * sizeof(int));
    int i = 0;
    postOrder(root, a, &i);

    return a;
}

  通过上面的题我们可以发现，二叉树很多操作都是基于递归实现的。所以要学好二叉树，必然要想掌握好递归。如果递归不熟悉就画递归图，多画几次就熟悉了。