二叉树常见算法题（单值二叉树、二叉树的最大深度、反转二叉树、判断两颗二叉树是否相同、对称二叉树、一颗二叉树是否是另一颗二叉树的子树）

二叉树常见算法题（单值二叉树、二叉树的最大深度、反转二叉树、判断两颗二叉树是否相同、对称二叉树、一颗二叉树是否是另一颗二叉树的子树）

这里的代码都是递归实现的，再强调下二叉树的概念，二叉树的构成有两种情况：

1、空树

2、根节点 + 左子树 + 右子树（这里的左子树和右子树又是一颗二叉树）

可以看出二叉树就是递归定义的，下面的算法题中大多都要用到这个思想。

一、单值二叉树 

1、题目要求：

2、解法：

这个也就是遍历二叉树，然后判断它是否和根节点的值相同，前序、中序、后序遍历都可以。

3、代码：

bool _isUnivalTree(struct TreeNode* root,int num){
    if(root == NULL){
        return true;
    }
    //检查根节点
    if(root->val != num){
        return false;
    }
    //递归检查左右子树
    return _isUnivalTree(root->left,num)&&
            _isUnivalTree(root->right,num);
}

bool isUnivalTree(struct TreeNode* root){
    
    if(root == NULL){
        return true;
    }
    return _isUnivalTree(root,root->val);
}

二、二叉树的最大深度

1、题目要求 

2、解题思路

最大深度 = 1 + 左子树的最大深度和右子树的最大深度中较大的一个（注意递归思想的建立）

3、代码

int maxDepth(struct TreeNode* root){
    if(root == NULL){
        return 0;
    }
    int leftHight = maxDepth(root->left);
    int rightHight = maxDepth(root->right);
    return leftHight > rightHight ? leftHight + 1:rightHight + 1;
}

三、反转二叉树

1、题目要求

 2、解题思路

从下往上看，其实就是把每一个节点的左子树和右子树交换一下。我们就可以遍历每一个节点然后交换它们的左右子树，现在要思考的是遍历的次序，仔细观察就会发现这里只能选择前序和后序遍历，因为中序遍历的话会把有些节点的左右孩子反转两次。

3、代码

void _invertTree(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    //递归反转左子树和右子树
    _invertTree(root->left);
    _invertTree(root->right);
     //交换左右孩子节点
    struct TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
}

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

四、判断两颗二叉树是否相同

1、题目要求 

2、解题思路

二叉树分为三部分，根节点、左子树和右子树，如果两颗二叉树相同的话那么这三部分都相同，根节点是否相同好判断，判断左子树和右子树时递归调用这个方法就可以了。

3、代码

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;
    }
    //p和q的左子树相同，右子树也相同
    return isSameTree(p->left,q->left)&&
           isSameTree(p->right,q->right);
}

五、对称二叉树

2、解题思路

观察就会发现，一颗二叉树是否对称，只用判断左子树和右子树是否对称，所以函数的参数就是两颗子树的根节点根。要判断左树和右数是否对称，其实只用判断左树的左子树和右树的右子树是否对称  且  左树的右子树和右树的左子树是否对称，想到这里其实递归的点就已经出现了，不要犹豫，试着写下去。

3、代码

bool _isSymmetric(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 _isSymmetric(left->left,right->right)&&
           _isSymmetric(left->right,right->left);
}

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

六、判断一棵树是否另一棵树的子树

1、题目要求2 

2、解题思路

一棵树是另一棵树的子树的话，有三种情况：这棵树等于另一棵树；这棵树等于另一棵树的左子树；这棵树等于另一棵树的右子树。这里就已经形成了递归的点了。判断两棵二叉树是否相同的方法上面已经写过了。

3、代码：

bool isSeemTree(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 isSeemTree(root1->left,root2->left)&&
           isSeemTree(root1->right,root2->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL && subRoot == NULL){
        return true;
    }
    if(root == NULL){
        return false;
    }
    if(subRoot == NULL){
        return true;
    }
    //判断root和subBoot是否是相同的树，相同则返回true
    if(isSeemTree(root,subRoot)){
        return true;
    }
    //再递归检测root的左子树或者右子树是否和subRoot相同
    return isSubtree(root->left,subRoot)||
           isSubtree(root->right,subRoot);
}