【数据结构与算法】二叉树基础OJ -- 上 (巩固提高)-1https://developer.aliyun.com/article/1456936
leetcode 144.二叉树的前序遍历(需要数组存储)
题目来源:144. 二叉树的前序遍历 - 力扣（LeetCode）
题目描述:
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例:
解题思路：
首先用TreeSize函数算出二叉树的节点数量,具体实现看这篇文章：http://t.csdnimg.cn/DvuEU
接着用*returnsize这个值接收，为什么要解引用?因为传过来的是size的地址-->&size
图解在这：实现其main函数:
接着malloc一块空间，定义指针int*a指向，定义变量i，接着传入preorder函数,进行前序遍历，之后返回a的地址。
代码实现：
int TreeSize(struct TreeNode* root) { return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right)+1; } 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= malloc(*returnSize*sizeof(struct TreeNode)); int i=0; preorder(root,a,&i); return a; }
执行：
关于此题有两个疑问:
1.用局部变量，下面的这个代码可以吗?
int TreeSize(struct TreeNode* root) { return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right)+1; } void _preorder(struct TreeNode* root, int* a,int i) { if (root == NULL) return; //用指针的方式是为了不在不同栈帧内创建i 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)); int i = 0; _preorder(root,a,i); return a; }
结果是不行，为什么?用局部变量就不行吗？
以下是我的理解:
2.全局变量可以吗？
可以，但是先列举问题:
解析：
虽然全局变量 i 在定义时已经被初始化为 0，但是全局变量的赋值操作只会在程序启动时执行一次。每次调用 _preorder 函数时，由于没有显式地给 i 赋新的值，i 的值会保持上一次调用结束时的值。这样会导致多次调用 _preorder 函数时，节点值被存储在错误的位置，结果可能不符合预期。 因此，在函数内部显式地给 i 赋值为 0，可以确保每次调用 _preorder 函数时都从数组 a 的开头位置开始存储节点的值，避免出现错误的索引位置。
leetcode 572.另一棵树的子树
题目来源：572. 另一棵树的子树 - 力扣（LeetCode）
题目描述:
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例:
解题思路:
首先，判断 root 是否为 NULL，如果是，则不存在子树，返回 false。 接着，调用 isSameTree 函数，判断 root 和 subRoot 是否相同，如果是，则 subRoot 是 root 的子树，返回 true。 如果以上条件都不满足，递归调用 isSubtree 函数，分别判断 subRoot 是否是 root 的左子树的子树，或者是 root 的右子树的子树。只要有一边存在子树，就返回 true。 如果都不满足，则 subRoot 不是 root 的子树，返回 false。
图解：
代码实现:
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)) { return true; } return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot); }
代码执行:
