–oj链接
题解:
1.判断根的左孩子的值与根结点是否相同。
2.判断根的右孩子的值与根结点是否相同。
3.判断以根的左孩子为根的二叉树是否是单值二叉树。
4.判断以根的右孩子为根的二叉树是否是单值二叉树。 若满足以上情况,则是单值二叉树。
注:空树也是单值二叉树。
代码:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isUnivalTree(TreeNode* root) { if(root==NULL)//根为空,是单值二叉树 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);//左子树是单值二叉树并且右子树是单值二叉树(递归) } };
–oj链接
题解:
判断两棵二叉树是否相同,也可以将其分解为子问题:
1.比较两棵树的根是否相同。
2.比较两根的左子树是否相同。
3.比较两根的右子树是否相同。
代码:
//判断两棵二叉树是否相同 bool isSameTree(BTNode* p, BTNode* q) { if (p == NULL&&q == NULL)//两棵树均为空,则相同 return true; if (p == NULL || q == NULL)//两棵树中只有一棵树为空,则不相同 return false; if (p->data != q->data)//两棵树根的值不同,则不相同 return false; return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);//两棵树的左子树相同并且右子树相同,则这两棵树相同 }
–oj链接
题解:
要判断某二叉树是否是对称二叉树,则判断其根结点的左子树和右子树是否是镜像对称即可。若在遍历过程中发现镜像对称的某两个结点值不同,则无需继续遍历。
代码:
//判断镜像位置是否相等 bool travel(BTNode* root1, BTNode* root2) { if (root1 == NULL&&root2 == NULL)//红蓝轨迹同时遍历到NULL,函数返回 return true; if (root1 == NULL || root2== NULL)//红蓝指针中,一个为NULL,另一个不为NULL,即镜像不相等 return false; if (root1->val!= root2->val)//红蓝指针指向的结点值不同,即镜像不相等 return false; //子问题:左子树遍历顺序:先左后右,右子树遍历顺序:先右后左。若两次遍历均成功,则是对称二叉树 return travel(root1->left, root2->right) && travel(root1->right, root2->left); } //对称二叉树 bool isSymmetric(BTNode* root) { if (root == NULL)//空树是对称二叉树 return true; return travel(root->left, root->right);//判断镜像位置是否相等 }
–oj链接
题解:
思路:
一个树是另一个树的子树则要么这两个树相等,要么这个树是左树的子树,要么这个树的右树的子树。
用两层递归来实现:
isSameTree函数用于递归检查需要判断的树对应结点是否相同(即判断相同二叉树);
isSubtree函数则用于判断subRoot 是否为root的子树;
代码:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ //检验这两棵树是否相同 bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(p==NULL&&q==NULL) return true; if(p==NULL||q==NULL) return false; if(p->val!=q->val) return false; return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right); } //判断subRoot 是否为root的子树 bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){ if(root==NULL)//空树,不可能是与subRoot相同(subRoot非空) return false; if(isSameTree(root,subRoot))//以root和subRoot为根,开始比较两棵树是否相同 return true; //判断root的左孩子和右孩子中是否有某一棵子树与subRoot相同 return isSubtree(root->left,subRoot)|| isSubtree(root->right,subRoot); }
–oj链接
题解:
根据前序遍历所得到的字符串,我们可以很容易地将其对应的二叉树画出来:
我们可以依次从字符串读取字符:
1.若该字符不是#,则我们先构建该值的结点,然后递归构建其左子树和右子树。
2.若该字符是#,则说明该位置之下不能再构建结点了,返回即可。
构建完树后,使用中序遍历打印二叉树的数据即可。
#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { struct TreeNode* left; struct TreeNode* right; char data; }TreeNode; //创建树 TreeNode* CreateTree(char* str, int* pi) { if(str[*pi] == '#')// { (*pi)++; return NULL; } //不是NULL,构建结点 TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->data = str[*pi]; (*pi)++; //递归构建左子树 root->left = CreateTree(str, pi); //递归构建右子树 root->right = CreateTree(str, pi); return root; } //中序遍历 void Inorder(TreeNode* root) { if(root == NULL) return; Inorder(root->left); printf("%c ", root->data); Inorder(root->right); } int main() { char str[100]; scanf("%s", str); int i = 0; TreeNode* root = CreateTree(str, &i); Inorder(root); return 0; }
–oj链接
题解:
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前
思路:
1.首先计算二叉树中结点的个数,便于确定动态开辟的数组的大小。
2.遍历二叉树,将遍历结果存储到数组中。
3.返回数组。
代码:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int TreeSize(struct TreeNode* root)//求树的结点个数 { if(root==NULL) return 0; return TreeSize(root->left)+TreeSize(root->right)+1; } void _preorderTraversal(struct TreeNode* root,int *arr,int *pi)//将树中结点的值放入数组 { if(root==NULL) { return; } //前序遍历 arr[(*pi)++]=root->val;//先将根结点的值放入数组 _preorderTraversal(root->left,arr,pi);//再将左子树中结点的值放入数组 _preorderTraversal(root->right,arr,pi);//最后将右子树中结点的值放入数组 } int* preorderTraversal(struct TreeNode* root,int *returnSize) { *returnSize=TreeSize(root); int *arr=malloc(sizeof(int)* *returnSize); int i=0; _preorderTraversal(root,arr,&i); return arr; }
中序和后序遍历原理差不多,只在递归顺序有差别
–oj链接
代码:
//求树的结点个数 int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } //将树中结点的值放入数组 void inorder(struct TreeNode* root, int* arr, int* pi) { //中序遍历 if (root == NULL)//根结点为空,直接返回 return; inorder(root->left, arr, pi);//先将左子树中结点的值放入数组 arr[(*pi)++] = root->val;//再将根结点的值放入数组 inorder(root->right, arr, pi);//最后将右子树中结点的值放入数组 } int* inorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = TreeSize(root);//值的个数等于结点的个数 int* arr = (int*)malloc(sizeof(int)*(*returnSize)); int i = 0; inorder(root, arr, &i);//将树中结点的值放入数组 return arr; }
–oj链接
代码:
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } //将树中结点的值放入数组 void postorder(struct TreeNode* root, int* arr, int* pi) { //后序遍历 if (root == NULL)//根结点为空,直接返回 return; postorder(root->left, arr, pi);//先将左子树中结点的值放入数组 postorder(root->right, arr, pi);//最后将右子树中结点的值放入数组 arr[(*pi)++] = root->val;//再将根结点的值放入数组 } int* postorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = TreeSize(root);//值的个数等于结点的个数 int* arr = (int*)malloc(sizeof(int)*(*returnSize)); int i = 0; postorder(root, arr, &i);//将树中结点的值放入数组 return arr; }