手撕一棵树之-----二叉树常见OJ面试题

说明：对二叉树知识不熟悉和遗忘的小伙伴可以看我往期博客点击——【数据结构入门】二叉树(BinaryTree) 详解（链式、顺序、初始化、遍历、高度、节点个数、排序）查看。

所有题解为本人思考的思路，欢迎各位51CTO的大佬评论指点和纠错分享更多解题思路~~~。 

1.二叉树oj—单值二叉树

解题思路：

整体采用分治的思想。不想当打工人，我是领导指导下面的手下，我和我的直系手下比较，比较值相等那么没问题，那么递归下去，我的直系手下和他自己的直系手下比较，只要发现val不相等那么就返回flase。整个程序只要有一个false，那么答案就是false。 因为返回值是bool，所以可以可以不用存储中间所有的true和false，用这个语句实现 return isUnivalTree(root->left)&& isUnivalTree(root->right);

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct 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);
}

2.二叉树oj—二叉树的最大深度

解题思路：

求二叉树的最大深度，那么这一题就是求深度，深度我们就要用到深度优先遍历dfs，转化为从根节点出发，找出左子树最深和右子树最深，比较选出最深的长度，再加上根节点的1。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int maxDepth(struct TreeNode* root){
    //深度遍历 
    if(root==NULL)
    {
        return 0;
    }
    return fmax(maxDepth(root->left),maxDepth(root->right))+1;
}

3.二叉树oj—翻转二叉树

解题思路：

先序遍历下去，一层一层的下，然后左右子树交换，然后递归下去，再交换，实现了翻转二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* invertTree(struct TreeNode* root){
    if(root==NULL)
    {
        return root;
    }
  //临时节点
    struct TreeNode* tmp=root->left;
    root->left=root->right;
    root->right=tmp;
    //先序遍历
    invertTree(root->left);
    invertTree(root->right);

    return root;
}

4.二叉树oj—相同的树

解题思路：

整体是分治的思想。比较两个二叉树是否相等，不仅仅要在相同位置有节点，而且要值相等，如果都为空那么就是真，一个为空一个不为空，那么肯定不相等为假，如果都不为空而且位置的值相等那么是真，但是得接着判断拿不到结果，所以取方面，当都不为空而且位置得值不相等，那么就是假。第一课数递归左子树和第二棵树得左子树比，右子树和右子树比，保证位置是一直相同的。

/**
 * 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(q->val != p->val)
        {
            return false;
        }
        //走到这里p和q的值相等
        //分治 交给下面的去比
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

5.二叉树oj—二叉树的前序遍历

解题思路：

本题需要返回一个数组，那么肯定需要开辟一个数组，来存我们先序遍历读到的值，然后还要返回这个数组的长度，我们通过前面的自己写一个求二叉树的函数，求出长度 ，再进行前序遍历，访问到NULL就返回，不是空那么我就存起来。

/**
 * 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)      // 求数的总共结点个数
{
    return root==NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}
//前序遍历   根左子树右子树     i的这个传递 如果不传指针 那么无法改变  如果在递归里面要++ 一定要传指针
void preorder(struct TreeNode* root,int* a,int* i)
{
    if(root==NULL)
    return;
    //访问到根节点 并把值放到数组里面
    a[(*i)++]=root->val;
    preorder(root->left,a,i);
    preorder(root->right,a,i);

}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    * returnSize=TreeSize(root);
    //动态开辟一个数组 
    int*a =(int*)malloc((*returnSize)*sizeof(int));
    //preorderTraversal 为什么不递归这个呢 如果递归这个我们每次递归都要动态开辟一个数组 这样空间是浪费的
    //把前序遍历的元素都放到数组里面
    int i=0;
    preorder(root, a, &i);

    return a;


}

6.二叉树oj—对称二叉树

解题思路：

我们可以通过上题看出，一颗树对称的要求是啥，一颗树要对象，根结点的左孩子要和右孩子相等，并且左孩子的左孩子和右孩子的右孩子要相等，左孩子的右孩子和右孩子的左孩子要相等，这是我从实例1看出来的，那么如果根节点都是NULL，那么为true，只要有一个不为空 ，另一个为空，那么就是false，这个地方就是那个判断是不是一个相同树的味道。接下来就是p先进左子树，再q进右子树递归下去，然后就是p进右子树，q进左子树递归下去。

bool isMirror(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)
        return true;

    if (p == NULL || q == NULL)
        return false;
    //最关键的理解地方 第一定是左子树和右子树
    return p->val == q->val && isMirror(p->left, q->right) && isMirror(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root)
{
    if (root == NULL)
        return true;

    return isMirror(root->left, root->right);
}

7.二叉树oj—另一棵树的子树

解题思路：

这一题还是使用分治的思路，模型和相同的树一样，变化的是左边那么大树，如果判断了不相等那么就要往左子树和右子树进行遍历再和右边的树进行判断。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//拿每一个根结点和右边树比
bool isSameTree(struct TreeNode* t1, struct TreeNode* t2)
{
    //都为NULL 那么返回true
    if(t1 == NULL && t2 == NULL)
        return true;
    //一个为空 另一个不为空 那么就是不相等
    if(t1 == NULL || t2 == NULL)
        return false;

    return t1->val == t2->val
        && isSameTree(t1->left, t2->left)
        && isSameTree(t1->right, t2->right);
}

bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
    if(t == NULL)
        return true;

    if(s == NULL)
        return false;

    if(s->val == t->val && isSameTree(s, t))
        return true;

    return isSubtree(s->left, t) 
        || isSubtree(s->right, t);
}

8.二叉树oj—二叉树遍历

#include <stdio.h>
typedef struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

TreeNode* CreatTree(char* arr,int* i)
{
    if(arr[*i]=='#')
    {
        return NULL;
    }
    else {
        TreeNode* root=(TreeNode*)malloc(sizeof(TreeNode));
        root->val=arr[*i];
        ++(*i);
        root->left=CreatTree(arr,i);
         ++(*i);
         root->right=CreatTree(arr,i);
         return root;
    }

}
//中序遍历
void InOrder(TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
int main() {
    char arr[100]={0};
    scanf("%s",arr);

    int i=0;
    TreeNode* root=CreatTree(arr,&i);
    InOrder(root);
    return 0;
}

大佬互访，一键三连~~~

【文章原创作者：武汉网页设计 http://www.1234xp.com/wuhan.html 欢迎留下您的宝贵建议】