1. 首页
  2. 博客
  3. 二叉树初阶OJ题（内附递归图解，思路）

二叉树初阶OJ题（内附递归图解，思路）

1.单值二叉树

解题思路

1.判断根的左孩子的值与根结点是否相同。
2.判断根的右孩子的值与根结点是否相同。
3.判断以根的左孩子为根的二叉树是否是单值二叉树。
4.判断以根的右孩子为根的二叉树是否是单值二叉树。
若满足以上情况，则是单值二叉树。

代码实现

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    /*if(root->left&&root->val!=root->left->val)
    {
        return false;
    }
    if(root->right&&root->val!=root->right->val)
    {
        return false;
    }
     return isUnivalTree(root->left)&&isUnivalTree(root->right);*/
    if((root->left&&root->val!=root->left->val)||(root->right&&root->val!=root->right->val))
    {
         return false;
    }
     else
     {
        return isUnivalTree(root->left)&&isUnivalTree(root->right);
     }
}

>

注意：如果你和起来写，if里面应该是||而不是&&，因为当你一个其中一个不相等的时候就肯定不是单值二叉树了，而且如果左孩子和根相等右孩子和根不相等（或者是相反的情况），这样也会出问题。

图解递归

随着学习的深入，这儿并没有画详细的递归过程，我直接在树的结构上把递归过程标了出来，大家配合右边的代码应该也可以很容易理解。

2.二叉树的最大深度

解题思路

子问题：
1.若为空，则深度为0。
2.若不为空，则树的最大深度 = 左右子树中深度较大的值 + 1。

代码实现

int Max(int a, int b)
{
    return a > b ? a : b;
}

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

图解递归

3.翻转二叉树

解题思路

思路1：

1.翻转左子树。
2.翻转右子树。
3.交换左右子树的位置。

代码实现

//翻转二叉树
BTNode* invertTree(BTNode* root)
{
    if (root == NULL)//根为空，直接返回
        return NULL;
    BTNode* left = invertTree(root->left);//翻转左子树
    BTNode* right = invertTree(root->right);//翻转右子树
    //左右子树位置交换
    root->left = right;
    root->right = left;
    return root;
}

思路2：

翻转每棵树的左右孩子节点

代码实现

struct TreeNode* invertTree(struct TreeNode* root){

    //翻转每棵树的左右节点
    if(root==NULL)
    {
        return NULL;
    }
    else
    {
        struct TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        invertTree(root->left);
        invertTree(root->right);
    }
    return root;
}

图解递归

解法1递归分析

解法二图解递归

4.对称二叉树

解题思路

>

要判断一棵树是否是对称二叉树，首先要判断根的左孩子和右孩子是否相等，然后判断以左孩子为根的左孩子和以右孩子为根的右孩子是否相等，判断以右孩子为根的左孩子和以左孩子为根的右孩子是否相等，若有一处不等，则不是对称二叉树。

代码实现

bool _isSymmetric(struct TreeNode* leftroot,struct TreeNode* rightroot)
{
    if(leftroot==NULL&&rightroot==NULL)
    {
        return true;
    }
    if(leftroot==NULL||rightroot==NULL)
    {
        return false;
    }
    if(leftroot->val!=rightroot->val)
    {
        return false;
    }
    return _isSymmetric(leftroot->left,rightroot->right)
         &&_isSymmetric(leftroot->right,rightroot->left);

}

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

>

注意：这里要直接递归题目中给的这个函数是不好实现这个题目的，因为这个函数只能接收一个指针，而我们要的效果是比较两个指针指向的val，所以要写一个子函数来协助我们实现。

图解递归

5.两个树是否相同

解题思路

在写过之前对称二叉树那题之后，这题就很简单了，首先我们判断两个树的根节点是否相同，然后判断左子树是否相同，再判断右子树是否相同。

代码实现

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);
}

图解递归

6.二叉树的前序遍历

解题思路

这道题的前序遍历和我们之前遍历二叉树时所说的前序遍历是不一样的，遍历时的前序遍历时将其打印出来，而这题这将它们存到一个动态开辟的数组中。

其实分析到这，解法也就呼之欲出了：我们首先要计算一下这棵树有多少个结点，方便我们之后动态开辟一个数组，然后采用前序遍历，不过其中我们不应该把他打印出来，而是放到我们开辟的数组中。

代码实现

int BinarySize(struct TreeNode* root)
 {
     if(root==NULL)
     {
         return 0;
     }
     else
     {
         return BinarySize(root->left)+BinarySize(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){
    int size=BinarySize(root);
    int *arr=(int*)malloc(sizeof(int)*size);
    int i=0;
    _preorderTraversal(root,arr,&i);
    *returnSize=size;
    return arr;
}

注意：这里传i时一定要传地址，不然在递归返回的过程中，下面递归中i的值不会影响到返回时i的值。

这里我们就不画出递归过程了，因为其实和之前的前序遍历的递归区别不大，所以不懂得小伙伴可以去看看博主之前一篇关于二叉树遍历的文章。

7.二叉树的遍历及构建

解题思路

>

首先在解这题时，我们要知道一个点，二叉树的构建一般情况下要给出中序遍历在结合一个前序遍历或者是后序遍历才是可以重建出来的，因为前序或者后序可以用来确定根节点，而中序可以在此基础上用来确定左子树和右子树，这样慢慢分析下去，可以重建出一个二叉树，但是如果只给一个前序遍历，一般情况下是肯定重建不出来的，特殊情况：前序遍历中有空节点是可能重建出来的。

当你分析出来这个过程时，其实这题也就不难了。
1.若该字符不是#，则我们先构建该值的结点（也就相当于先构建根节点），然后递归构建其左子树和右子树。
2.若该字符是#，则说明该位置之下不能再构建结点了，返回即可。

代码实现

void MiddleOrder(BT* n1)
{
    if(n1)
    {
    MiddleOrder(n1->left);
    printf("%c ", n1->x);
    MiddleOrder(n1->right);
    }
}


BT* CreatTree(char* arr,int* pi)
{
    if(arr[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    BT* root=(BT* )malloc(sizeof(BT));
    root->left=NULL;
    root->right=NULL;
    root->x=arr[(*pi)++];
    root->left=CreatTree(arr,pi);
    root->right=CreatTree(arr,pi);
    return root;
}
int main()
{
    char arr[100]={0};
    scanf("%s",arr);
    int i=0;
    struct BinaryNode* root=CreatTree(arr,&i);
    MiddleOrder(root);
}

图解递归

8.平衡二叉树

解题思路

解题思路1：

判断每个节点的左右子树高度差是否大于1

代码实现

int Max(int a, int b)
{
    return a > b ? a : b;
}

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

bool isBalanced(struct TreeNode* root){

    if(root==NULL)
    {
        return true;
    }
     int rootleftDepth=BinaryDepth(root->left);
     int rootrightDepth=BinaryDepth(root->right);



    return abs(rootleftDepth-rootrightDepth)<2&&isBalanced(root->left)&&isBalanced(root->right);
}

时间复杂度：O（n^2）

解题思路2：

采用后序遍历：
1.从叶子结点处开始计算每课子树的高度。（每棵子树的高度 = 左右子树中高度的较大值 + 1）
2.先判断左子树是否是平衡二叉树。
3.再判断右子树是否是平衡二叉树。

4.若左右子树均为平衡二叉树，则返回当前子树的高度给上一层，继续判断上一层的子树是否是平衡二叉树，直到判断到根为止。（若判断过程中，某一棵子树不是平衡二叉树，则该树也就不是平衡二叉树了）

代码实现

bool _isBalanced(struct TreeNode* root, int* ph)
{
    if (root == NULL)//空树是平衡二叉树
    {
        *ph = 0;//空树返回高度为0
        return true;
    }
    //先判断左子树
    int leftHight = 0;
    if (_isBalanced(root->left, &leftHight) == false)
        return false;
    //再判断右子树
    int rightHight = 0;
    if (_isBalanced(root->right, &rightHight) == false)
        return false;
    //把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
    *ph = Max(leftHight, rightHight) + 1;

    return abs(leftHight - rightHight) < 2;//平衡二叉树的条件
}
//判断二叉树是否是平衡二叉树
bool isBalanced(struct TreeNode* root)
{
    int hight = 0;
    return _isBalanced(root, &hight);
}

图解递归

解法一图解递归

解法二图解递归

9.另一棵树的子树

解题思路

依次判断以 root 中某一个结点为根的子树是否与subRoot相同。

代码实现

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);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
      if(root==NULL)
      {
          return false;
      }
      if(isSameTree(root,subRoot)==1)
      {
          return true;
      }
      else
      {
          return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
      } 
}

这题的递归其实也就是issameTree的递归，在之前的那题中已经图解过它的递归了，这儿就不再赘述了。

二叉树初阶OJ题（内附递归图解，思路）介绍到这里，更多教程学习请参考编程字典教程和问答部分，谢谢大家对编程字典的支持。

原文链接：https://blog.csdn.net/IamGreeHand/article/details/120215132

热门标签