二叉树基础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;
}

---

今天就到这里啦！