目录

1.单值二叉树

2.相同的树

3. 二叉树的前序遍历

1.单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

力扣https://leetcode.cn/problems/univalued-binary-tree/description/

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

这段代码的作用是判断给定的二叉树是否是单值二叉树，返回 true 或 false。该实现使用了递归的方法。

具体来说，该函数的实现思路为：

1. 如果当前节点为空，则返回 true。

2. 判断左子树的值是否与当前节点的值相等，如果不相等则返回 false。

3. 判断右子树的值是否与当前节点的值相等，如果不相等则返回 false。

4. 递归地对左右子树进行同样的操作，并返回结果的与运算。

总体来说，该实现大致符合单值二叉树的定义，时间复杂度为 O(N)，其中 N 指二叉树的节点数。

2.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

力扣https://leetcode.cn/problems/same-tree/

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

该函数的作用是判断给定的两个二叉树是否相同，即两个二叉树具有相同的结构和节点值，返回 true 或 false。

该函数的实现思路是：

1. 如果两个二叉树都为空，则它们相等，返回 true。

2. 如果其中一个二叉树为空，而另一个不为空，则它们一定不相等，返回 false。

3. 比较两个非空二叉树的根节点值是否相等，如果不相等，则它们不相等，返回 false。

4. 递归比较两个二叉树的左右子树，并返回结果的与运算。

总体来说，该实现大致符合判断两个二叉树是否相同的定义，时间复杂度为 O(N)，其中 N 指二叉树的节点数。

3. 二叉树的前序遍历

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

力扣https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

int TreeSize(struct TreeNode*root)
{return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}void preorder(struct TreeNode*root ,int*a,int* pi)
{if(root==NULL)return;a[(*pi)++]=root->val;preorder(root->left,a, pi);preorder(root->right,a, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize){*returnSize=TreeSize(root);int*a=(int*)malloc((*returnSize)*sizeof(int));int i=0;preorder(root,a,&i);return a;}

1. TreeSize() 函数用于计算二叉树的节点数量，采用递归方式实现。当传入的根节点为 NULL 时，返回节点数量 0；否则，递归遍历左右子树，并将节点数量+1，最后返回整个二叉树的节点数量。

2. preorder() 函数用于实现二叉树的前序遍历，并将遍历结果存储在数组 a 中。采用递归方式实现。当传入的根节点为 NULL 时，直接返回；否则，将当前节点的值存储到数组 a 中，并依次递归遍历左右子树，并将遍历位置的引用 i 加 1。

3. preorderTraversal() 函数是前序遍历的入口函数，它首先调用 TreeSize() 函数计算二叉树的节点数量，并将结果存储在参数 returnSize 中。然后，函数根据节点数量动态分配大小为 returnSize 的数组 a，并将数组作为参数传递给 preorder() 函数，以便前序遍历的结果可以存储在数组中。最后，函数返回数组 a 的首地址，即二叉树前序遍历的结果。

特别注意

a[(*pi)++]=root->val;

这句代码的作用是将当前节点的值存储到数组a中，并将遍历位置的引用i加1。其中，pi是指向i的指针，因为在递归调用中，i的值会不断变化，如果直接传递i的值，则无法正确记录遍历的位置。

*pi表示获取pi所指向的内存空间中存储的值，即i的值。因此，(*pi)++表示将i的值加1，并将加1后的结果存储回i中；同时，将当前节点的值root->val存储到a[i]中，实现了在前序遍历的过程中将节点的值依次存储到数组中。

在递归中，函数可能会被多次嵌套调用。每一次嵌套调用都会创建一个新的栈帧，该栈帧包含了当前函数的局部变量、参数等信息。在这个新的栈帧中，将重新定义一个新的变量 i，并且在这个新的变量 i 上进行加减等操作。

假设我们要求一个二叉树的前序遍历。在遍历根节点、左子树和右子树时，我们需要知道当前遍历数组的索引位置。为了记录这个索引位置，我们在函数中定义了一个变量 i，可以看做是一个指针，用来指向当前数组中待存放遍历结果的位置。

在函数执行过程中，我们需要不断更新这个变量 i 的值，以便将遍历结果存储到正确的位置上。但是，在递归中，每一次调用都会创建一个新的栈帧和新的变量 i，这就导致了变量 i 在不同的栈帧中是不同的，而且在递归过程中这些变量 i 的值会不断变化。

例如，在遍历完根节点之后，我们需要遍历左子树。此时我们会调用 preorder() 函数来遍历左子树。在左子树的 preorder() 函数调用中，变量 i 是从根节点的 preorder() 函数中继承而来的，它记录了遍历数组中左子树遍历结果存放的起始位置。但是，在递归调用过程中，变量 i 的值是会不断变化的，因为在递归调用时会重新定义一个新的变量 i。也就是说，当我们递归调用到左子树的左子树时，新的变量 i 只会记录从左子树左子树开始的存储位置，而不是原来记录左子树存储位置的变量 i，这样就保证了变量 i 的值在不同的函数调用中是不同的，而且在递归过程中这些变量 i 的值会不断变化。