二叉树基础oj练习（对称二叉树、翻转二叉树、另一棵树的子树二叉树的构建及遍历）

1.对称二叉树

传送门

题目详情

代码

bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2)
{
    if(root1==NULL&&root2==NULL)//都为空
        return true;
    if(root1==NULL||root2==NULL)//一个是空一个不是
        return false;
    if(root1->val!=root2->val)
        return false;     //根部分已经判断完成

        return _isSymmetric(root1->left,root2->right)
        &&_isSymmetric(root1->right,root2->left);
}

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

思路

我们以“相同的树”那题思路拓展开，先创建子函数，传入左节点和右节点（要看是否对称，比较两边）
大的思路：先看根存在或相同否，根判断完后。开始左子树，递归调用函数。接着右子树也同理
聚焦于递归：函数的主体只是比较那个“根”的情况，但是每个子节点也是根，递归调用后，他们在他们的函数里就是根（所以来判断他们的相等或者为空情况），最后都是遇到空（到了整体树的叶），就停止了

2.翻转二叉树

传送门

题目详情

代码

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

    struct TreeNode* root1=invertTree(root->left);
    struct TreeNode* root2=invertTree(root->right);
    root->left=root2;//真翻转
    root->right=root1;//真翻转
   return root;
}

思路

很明确的一点是：我们要从根节点开始，递归地对树进行遍历
具体的实现方法：叶子节点先开始翻转(叶子下面都是NULL，交换后也没意义，叶子也是利用那两条“真翻转”语句来进行交换，交换后返回，去进行上一级节点)。
宏观上：如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，就完成了
通过递归的方式翻转左子树和右子树，并将左子树指向翻转后的右子树，右子树指向翻转后的左子树，最后返回当前节点

3.另一颗树的子树

传送门

题目详情

代码1

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

 }

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    {
        return false;
    }
    if(root->val==subRoot->val)
    {
        if(isSameTree(root,subRoot))
        {
            return true;
        }
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

思路1

我们借用一下isSameTree的代码（来判断两个树是不是相同的），这题也是看root的子树有没有跟subroot有没有相同的。还是先处理根（因为每个左右子树进去后也是根）
要是val一相同，再看是不是一个树，要是就返回true了，不是就看左子树和右子树是不是

代码2

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

 }

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

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

思路2

现在成了“三选一”了，也很好理解：三种情况有一种为真就返回true了
背后还是同一种思路不同的写法，背后的逻辑关系是一样的：看似少了一句root->val==subRoot->val，但是本身isSameTree就能进行跟是否相同的判断

4.二叉树的构建及遍历

传送门

题目详情

代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode { //节点
    BTDataType data;//数据
    struct BinaryTreeNode* left;//左孩子
    struct BinaryTreeNode* right;//右孩子
} TreeNode;


TreeNode* createTree(char* arr, int* pi) {
    if (arr[*pi] == '#' || arr[*pi] == '\0') {
        (*pi)++;
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    assert(root);
    root->data = arr[*pi];
    (*pi)++;
    root->left = createTree(arr, pi);
    root->right = createTree(arr, pi);
    return root;
}

void PreOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    PreOrder(root->left);
    printf("%c ", root->data);
    PreOrder(root->right);
}

int main() {
    char arr[100] = { 0 };
    scanf("%s", arr);
    int i = 0;
    TreeNode* root = createTree(arr, &i);
    PreOrder(root);

    return 0;
}

---

今天就到这里啦！