异世界历险之数据结构世界（二叉树-leetcode）-EW帮帮网

前言

实战演练

单值二叉树。OJ

检查两颗树是否相同。OJ

对称二叉树OJ

Question

Question 1

在这里插入图片描述

Method

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

Topic analysis

根节点与左右孩子比较
若当前节点不满足单值条件直接返回 false
否则递归检查子树，所有子树都满足才返回 true

递归展开：

最外层调用 isUnivalTree(root)：
检查根节点：
root != NULL
root->val == 1
继续检查左右子树。
递归检查左子树：isUnivalTree(root->left)
递归检查右子树：isUnivalTree(root->right)

递归调用 isUnivalTree(root->left)：
检查左子树的根节点：
root->val == 1，root->left->val == 1，root->right->val == 1
继续递归检查左右子树。
递归检查左子树的左子树：isUnivalTree(root->left->left)
递归检查左子树的右子树：isUnivalTree(root->left->right)

递归调用 isUnivalTree(root->left->left) 和 isUnivalTree(root->left->right)：
这两个节点都是叶子节点，值都为 1，都返回 true。
因此，isUnivalTree(root->left) 返回 true。

递归调用 isUnivalTree(root->right)：
检查右子树的根节点：
root->val == 1，右子树也满足条件，递归调用 isUnivalTree(root->right->left) 和 isUnivalTree(root->right->right)。
因为 root->right 是叶子节点且值为 1，返回 true。

最终返回：
isUnivalTree(root) 会返回 isUnivalTree(root->left) && isUnivalTree(root->right)。
所以，最终结果是 true && true，返回 true。

Question2

在这里插入图片描述

Method

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

Topic analysis

比较空树的情况：
if (p == NULL && q == NULL) return true;
如果两棵树都为空，那么它们自然是相同的，返回 true。
其中一棵树为空：
if (p == NULL || q == NULL) return false;
如果其中一棵树为空，另一棵树不为空，那么它们不可能相同，返回 false。
当前节点的值不同：
if (p->val != q->val) return false;
如果当前节点的值不同，那么两棵树肯定不同，返回 false。
递归检查左右子树：
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
如果当前节点的值相同，我们就继续递归地检查左子树和右子树是否相同。
只有当左右子树都相同，整个树才能被认为是相同的，所以使用 && 运算符连接两个递归调用。

递归展开类似上道题目。
调用 isSameTree(root1, root2)：
比较根节点：1 == 1，继续检查左右子树。
递归调用 isSameTree(root1->left, root2->left)：

比较左子树根节点：2 == 2，继续检查左右子树。
递归调用 isSameTree(root1->left->right, root2->left->right)：
root1->left->right == NULL，root2->left->right == NULL，返回 true。
递归调用 isSameTree(root1->right, root2->right)：

比较右子树根节点：3 == 3，继续检查左右子树。
递归调用 isSameTree(root1->right->left, root2->right->left)：
root1->right->left == NULL，root2->right->left == NULL，返回 true。
递归调用 isSameTree(root1->right->right, root2->right->right)：
root1->right->right == NULL，root2->right->right == NULL，返回 true。
最终，因为所有的递归都返回了 true，所以 isSameTree(root1, root2) 返回 true。

Question3

在这里插入图片描述

Method

bool isMirror(struct TreeNode* t1,struct TreeNode* t2)
{
    if(t1==NULL && t2==NULL) return true;
    if(t1==NULL || t2==NULL) return false;
    if(t1->val != t2->val) return false;

    return isMirror(t1->left,t2->right) && isMirror(t1->right,t2->left);
}

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

Topic analysis

isMirror函数：
逻辑分析：
空树判断：如果两棵树都为空，说明它们是对称的，返回 true；如果其中一个为空，另一个不为空，说明它们不对称，返回 false。
节点值比较：如果两个节点的值不同，它们不可能对称，返回 false。
递归检查：
递归地检查左子树和右子树是否镜像对称，具体来说，t1->left 应该与 t2->right 对称，t1->right 应该与 t2->left 对称。

isSymmertric函数：
逻辑分析：
空树判断：如果树的根节点是 NULL，树自然是对称的，返回 true。
调用 isMirror：如果根节点不为空，我们就调用 isMirror 来判断左子树和右子树是否镜像对称。

实战演练

4.二叉树前序遍历
5.另一颗树的子树。

Question

Question4

在这里插入图片描述

Method

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

void Preorder(struct TreeNode* root,int*arr,int* i)
{   if(root == NULL) return ;
    arr[(*i)++] = root->val;
    Preorder(root->left,arr,i);
    Preorder(root->right,arr,i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int)*(*returnSize));
    int i = 0;
    Preorder(root,arr,&i);
    return arr;
}

Topic analysis

TreeSize 函数：
逻辑分析：
空树判断：如果当前节点为空（即树为空），则节点数为 0。
递归计算：如果当前节点不为空，递归地计算左子树和右子树的节点数，并加上当前节点的 1，得到整棵树的节点数。

PreOrder函数：
逻辑分析：
空树判断：如果当前节点为空，直接返回，不做任何操作。
访问根节点：将当前节点的值 root->val 存入数组 arr，并递增 i，表示数组的下一个位置。
递归遍历：首先递归遍历左子树，然后递归遍历右子树。

preorderTraversal函数:
逻辑分析：
计算树的节点数：首先调用 TreeSize(root)，得到树 root 的节点总数，并存储在 *returnSize 中。
分配内存：根据树的节点数，分配一个数组 arr，用于存储前序遍历的结果。
执行前序遍历：调用 Preorder(root, arr, &i) 来进行前序遍历，arr 用于存储结果，i 用来追踪当前存储的位置。
返回结果：最后返回存储前序遍历结果的数组 arr。

Error Reminder

在 Preorder 函数中，i 用来记录当前遍历到的节点位置（数组的下标）。我们通过递归遍历二叉树的每个节点，并将它们的值依次存入数组中。

为什么要传递指针而不是值？
递归函数的每次调用都会有一个独立的作用域。如果我们将 i 作为值传递，那么每次递归调用时 i 会被拷贝到一个新的变量，这意味着递归调用中的每个 i 都是独立的，它们不会相互影响。
但是，我们希望在递归过程中能够共享同一个 i 值，让它在每次递归时都能够“记住”之前的值，以便正确地更新数组的下标。这就需要传递 i 的指针，从而确保递归中的每个调用都操作的是同一个 i，而不是各自的副本。

具体分析：
传递值（错误方式）：
如果我们传递 i 的值，每次递归时，i 的副本会被创建，递归函数中的 i 会独立于父调用中的 i。这样在递归过程中，i 就不能准确地追踪遍历到的位置，导致数组下标出错。

void Preorder(struct TreeNode* root, int* arr, int i) {  // 错误，i 是值传递
    if (root == NULL) return;
    arr[i++] = root->val;
    Preorder(root->left, arr, i);  // 传递副本，不影响原来的 i
    Preorder(root->right, arr, i); // 同上
}

在这个例子中，i 的值会被传递给每个递归调用的副本，导致递归过程中的 i 在每一层都没有被正确更新，从而使得最终的数组存储位置错误。

传递指针（正确方式）：
当我们传递 i 的指针（int* i）时，所有递归调用都操作同一个 i。每次递归时，对 i 的更新都会影响到其他递归调用，确保下标位置不断递增。

void Preorder(struct TreeNode* root, int* arr, int* i) {  // 正确，i 是指针传递
    if (root == NULL) return;
    arr[(*i)++] = root->val;   // 操作同一个 i
    Preorder(root->left, arr, i);  // 递归，i 继续共享
    Preorder(root->right, arr, i); // 同上
}

这样，在每一次递归调用中，i 的更新都会影响到父函数的 i，确保递归遍历过程中数组的位置被正确更新。

Question5

在这里插入图片描述

Method

bool isSameTree(struct TreeNode* t1,struct TreeNode* t2)
{
   if(t1==NULL && t2==NULL) return true;
   if(t1==NULL || t2==NULL) return false;
   if(t1->val != t2->val) return false;

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

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

Topic analysis

第一个函数不作解释。
逻辑分析：
空树判断：如果 root 为空，说明无法找到子树 subRoot，返回 false。
完全匹配：如果 root 和 subRoot 完全相同，说明 subRoot 是 root 的子树，返回 true。此时使用 isSameTree 来比较两个树是否完全相同。
递归搜索：如果当前节点不匹配，递归检查左子树和右子树，看看 subRoot 是否出现在其中一个子树中。

递归展开：
调用 isSubtree(root, subRoot)：
检查 root 和 subRoot 是否完全相同。使用 isSameTree(root, subRoot)。
root->val == 3 和 subRoot->val == 4，值不同，返回 false。
继续递归检查 root 的左右子树。
递归调用 isSubtree(root->left, subRoot)：
root->left 的值是 4，与 subRoot 完全相同。此时，调用 isSameTree(root->left, subRoot)，返回 true。
因此，isSubtree(root, subRoot) 返回 true。

总结：这是补充的二叉树部分内容。

异世界历险之数据结构世界（二叉树-leetcode）

前言

实战演练

Question

Question 1

Method

Topic analysis

Question2

Method

Topic analysis

Question3

Method

Topic analysis

实战演练

Question

Question4

Method

Topic analysis

Error Reminder

Question5

Method

Topic analysis

网站公告

今日签到

热门文章

最新发布