【C】链式二叉树算法题2

目录

1  另一棵树的子树 

 1） 题目描述

示例1：

示例2：

2） 算法解析

3） 代码

2  二叉树的遍历

1） 问题描述

2） 算法解析

3） 代码

3  总结  

1  另一棵树的子树 

leetcode链接https://leetcode.cn/problems/subtree-of-another-tree/description/

 1） 题目描述

  给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

  二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

  该题目是想让你判断 root 这棵树中是否有 subRoot 这棵树，不管是相同的树，还是左子树中有与subRoot 相同的树或者是在右子树中有与 subRoot 相同的树，subRoot 都算是 root 的子树。

2） 算法解析

  该题目可以采用递归算法来解决。这道题的解决需要使用到前一篇文章里的相同的树的算法，因为判断 subRoot 是否是 root 的子树，本质上就是判断 root 里是否有与 subRoot 相同的树，具体算法思想描述如下：
  该递归算法可以抽象为 root 的左子树里是否有与 subRoot 相同的树或者右子树里是否有与 subRoot 相同的树，这个就是递归解决该问题的过程。边界条件共有两条：（1） 如果 root 本身是一棵空树，那么 root 里肯定没有与 subRoot 相同的树，直接返回 false；（2） 如果 root 这棵树本身就是与 subRoot 相同的树，说明 subRoot 是 root 的一棵子树，那就返回 true。

3） 代码

typedef struct TreeNode TreeNode;
 //判断相同的树
 bool isSameTree(TreeNode* p, 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) 
{
    //如果root为空，那就返回false
    if (root == NULL)
    {
        return false;
    }
    //如果两个结点对应的树是相同的树，返回true
    if (isSameTree(root, subRoot))
    {
        return true;
    }
    //判断subRoot是否是左子树或者右子树的子树
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

2  二叉树的遍历

leetcode链接https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

1） 问题描述

  给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

  这里看似是一个简单的前序遍历，但是其实没有那么简单，我们来看一下函数头部：

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    
}

  可以看到其返回值为 int* ，也就是一个指针，并不像之前我们写过的前序遍历一样返回值为 void。实际上这里是需要返回一个存储了节点前序遍历值的数组，所以返回值才为 int*。

2） 算法解析

  这里最大的难点就在与如何将前序遍历的结果存储在数组里面，而且所给的函数头部里面也有一个 returnSize 参数，通过名字可以看出来，该参数的作用实际上就是返回数组的大小，所以我们不仅需要将数组返回，还得计算数组中有多少元素，也就是二叉树里面有多少节点。所以我们需要首先计算二叉树里面节点的个数（在链式二叉树文章中提到过相关操作的实现），所以这里总共需要 3 个函数：

（1） TreeSize函数：用来计算二叉树里面节点的个数。

（2） PreOrder函数：用来进行前序遍历，将结果存储在数组中。

（3） preorderTraversal函数：用来创建数组，返回存储结果的数组。

  接下来我们来讲解如何将前序遍历的结果存储在数组中。

  可能开始我们想的是按照前序遍历的代码，只需将打印的地方改为向数组中存储值即可：

void PreOrder(TreeNode* root, int* arr)
{
  int i = 0;
  if (root == NULL)
  {
    return;
  }

  arr[i] = root->val;
  i++;
  PreOrder(root->left, arr);
  PreOrder(root->right, arr);
}
  

但是这样会存在一个问题，就是在不断递归的过程中，每次进入新的递归的时候，里面的 i 都会变成0，也就是总是往 arr[0] 位置存储前序遍历的结果，这里借助函数栈帧（每次调用函数时，会新开辟的一块空间，每个函数的空间是独立的）的概念来解释：

可以看到每次调用PreOrder函数，都会新开辟一块空间，所以其实里面的 i 都是属于不用空间的，一个 i 改变并不会影响另一个函数里面的 i ，所以每次递归调用函数 i 都是为 0 的。

  那么要想在递归过程中改变这个下标，我们就需要传递一个整形的地址，让其能够找到存储 arr 下标的空间，让存储空间里面的值改变，就会让下标随着递归的而改变了：

//arr为数组收元素的地址，pi为存储arr数组下标的地址
void PreOrder(TreeNode* root, int* arr, int* pi)
{
  if (root == nullptr)
  {
     return;
  }
 
  arr[(*pi)++] = root->val;
  PreOrder(root->left);
  PreOrder(root->right);
}

这里就可以通过一个指针变量 pi 来指向存储 arr 数组下标的空间（传参时传递一个值为 0 的整型的地址即可）， 这样通过 pi 就可以间接改变 arr 数组中的值了。

3） 代码

typedef struct TreeNode TreeNode;
 //先计算树的结点个数，依结点个数开辟数组空间
 int TreeSize(TreeNode* root)
 {
    if (root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
 }
//将前序遍历的序列存入数组中
void PreOrder(TreeNode* root, int* arr, int* pi)
{
    if (root == NULL)
    {
        return;
    }
    arr[(*pi)++] = root->val;
    //遍历左子树
    PreOrder(root->left, arr, pi);
    //遍历右子树
    PreOrder(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    *returnSize = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    if (arr == NULL)
    {
        perror("malloc fail！\n");
        exit(1);
    }
    int n = 0;
    PreOrder(root, arr, &n);

    return arr;
}

3  总结  

  在该题目中，我们解决了如何在递归过程中向数组中存储数据的问题。只需用一个指针变量间接改变即可。所以以后如果遇到类似问题，一定要想到利用指针来改变下标。

  当然，除了前序遍历，还有中序遍历和后序遍历，在讲解完前序遍历之后，相信这两个遍历也很简单了，可以自己尝试一下：
中序遍历https://leetcode.cn/problems/binary-tree-inorder-traversal/代码：

typedef struct TreeNode TreeNode;
 //返回树的结点个数
 int TreeSize(TreeNode* root)
 {
    if (root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
 }
//中序遍历树，把遍历数据存放在数组里面
void InOrder(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));
    if (arr == NULL)
    {
        perror("malloc fail！\n");
        exit(1);
    }
    int n = 0;
    InOrder(root, arr, &n);

    return arr;
}

后序遍历https://leetcode.cn/problems/binary-tree-postorder-traversal/description/代码：

typedef struct TreeNode TreeNode;
 //求节点个数
 int TreeSize(TreeNode* root)
 {
    if (root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
 }

//二叉树的后序遍历并将遍历结果保存到数组中
void PostOrder(int* arr, TreeNode* root, int* i)
{
    if (root == NULL)
    {
        return;
    }
    //遍历左子树
    PostOrder(arr, root->left, i);
    //遍历右子树
    PostOrder(arr, root->right, i);
    arr[(*i)++] = root->val;

}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);
    //根据二叉树节点空间开辟数组
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    int i = 0;
    PostOrder(arr, root, &i);

    return arr;
}