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; }
今天就到这里啦！
