二叉树习题

相同的树

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL) return true;//如果他们都是NULL证明是相同的树，返回true

    if(p==NULL||q==NULL) return false;//其中有一个是NULL

    //剩下的全是有值的节点
    if(p->val==q->val) return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    return false;

}
1
2
3
4
5
6
7
8
9
10

另一颗树的子树

bool isSameTree(struct TreeNode* p, struct TreeNode* q){

    if(p==NULL&&q==NULL) return true;
    if(p==NULL||q==NULL) return false;//其中有一个是NULL
    //剩下的全是有值的节点
    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){
    //如果root是NLULL证明subroot一定不是root的子树
    if(root==NULL) return false;

    if(root->val == subRoot->val)
        if(isSameTree(root,subRoot)) return true;//如果相等返回true
        //不相等向下递归，
        //不可以写成return isSameTree(root,subRoot);如果写成了这种形式，如果不相等的时候会直接返回false
        //但是此时他不能直接就结束
    //不相等
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

翻转二叉树

struct TreeNode* invertTree(struct TreeNode* root){
    if(root==NULL) return NULL;//当root为NULL的时候直接返回NULL
    //根据上图我们观察
    //如果是先交换跟节点，那么他的字节点应该就不能交换成现在的样子了
    //所以需要先交换其他的子节点，最后交换根节点
    //函数返回的是已经交换好的节点
    invertTree(root->left);
    invertTree(root->right);
    struct TreeNode* tem=root->left;
    root->left=root->right;
    root->right=tem;
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

对称二叉树

 bool ismirror(struct TreeNode* left,struct TreeNode* right)
 {
     if(left==NULL&&right==NULL) return true;
     if(left==NULL||right==NULL) return false;
     if(left->val!=right->val) return false;
     return ismirror(left->left,right->right)&&ismirror(left->right,right->left);
 }
 
bool isSymmetric(struct TreeNode* root){
    if(root==NULL) return true;
    if(root->left==NULL&&root->right==NULL) return true;
    if(root->left==NULL||root->right==NULL) return false;
    //都不是NULL
    return ismirror(root->left,root->right);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

前序遍历

 int TreeSize(struct TreeNode* root)
 {
     if(root==NULL) return 0;
     return TreeSize(root->left)+TreeSize(root->right)+1;
 }

void preorder(struct TreeNode* root,int* cnt,int* nums)
{
    //cnt表示当前位置
    if(root==NULL) return ;
    nums[(*cnt)++]=root->val;
    //preorder(root->left,cnt,nums),preorder(root->right,cnt,nums);   
    //向下递归的时候是对的，但是在向上返回的时候就会出现问题
    //因为形参的改变不影响实参

    preorder(root->left,cnt,nums),preorder(root->right,cnt,nums);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int n=TreeSize(root);
    int* nums=(int*)malloc(sizeof(int)*n);
    int cnt=0;
    preorder(root,&cnt,nums);
    *returnSize=n;
    return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26