做网站 工商 非法经营,网站建设与运营的公司,杭州网站制作排名,wordpress评论框函数讲了这么多数据结构相关的知识(可以看我的数据结构文章专栏):
抓紧刷题巩固一下了
目录
1.单值二叉树
题目描述
思路1
代码1
思路2 代码2
2.相同的树
题目描述
思路
代码
3.二叉树的前序遍历
代码 思路 1.单值二叉树
965. 单值二叉树 - 力扣#xff08;LeetCod…讲了这么多数据结构相关的知识(可以看我的数据结构文章专栏):
抓紧刷题巩固一下了
目录
1.单值二叉树
题目描述
思路1
代码1
思路2 代码2
2.相同的树
题目描述
思路
代码
3.二叉树的前序遍历
代码 思路 1.单值二叉树
965. 单值二叉树 - 力扣LeetCode
题目描述 思路1 利用递归 首先检查根与左右节点的值是否相等如果不相等就能直接返回false 都一样就依次进入左右子树开始检查子树。 对于每个节点它会检查其左子节点和右子节点的值是否与当前节点的值相同如果不同则返回 false。如果左右子树都满足条件则继续递归地检查左子树和右子树 递归的终止条件是当遍历到叶子节点时此时返回 true 代码1
bool isUnivalTree(struct TreeNode* root) {if(rootNULL)return true;if(root-left!NULLroot-left-val!root-val){return false;}if(root-right!NULLroot-right-val!root-val){return false;}return isUnivalTree(root-left)isUnivalTree(root-right);
} 思路2 首先检查根节点是否为空如果为空则直接返回 true 然后代码会递归地检查左子树和右子树。对于每个节点它会检查其左子节点和右子节点的值是否与当前节点的值相同如果不同则返回 false。同时它也会递归地检查左子树和右子树是否为unival树一旦不满足条件直接返回false 满足了就走到最后返回true 代码2
bool isUnivalTree(struct TreeNode* root) {if(rootNULL)//看根{return true;}if(root-left)//左子树不为空就先看左子树符合否{if(root-left-val!root-val||!isUnivalTree(root-left))return false;}if(root-right)//右子树不为空{if(root-right-val!root-val||!isUnivalTree(root-right))return false;}return true;
} 2.相同的树
100. 相同的树 - 力扣LeetCode
题目描述 思路
先根和根比比完再比左子树和右子树 1. 两者都是空时也相等 2. 左节点或右节点一个存在一个不存在返回false都存在不相等也是false 3.开始递归都是NULL时返回true或者返回false停止 代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(pNULLqNULL){return true;}if(pNULLq!NULL){return false;}if(qNULLp!NULL){return false;}if(p-val!q-val){return false;}bool left isSameTree(p-left,q-left);bool right isSameTree(p-right,q-right);return leftright;
} 3.二叉树的前序遍历
144. 二叉树的前序遍历 - 力扣LeetCode
代码
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : 1 TreeSize(root-left) TreeSize(root-right);
}void preorder(struct TreeNode* root, int* a, int* i)
{if (root NULL){return;}a[*i] root-val;(*i);preorder(root-left, a, i);preorder(root-right, a, i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {int n TreeSize(root);*returnSizen;int* a(int*)malloc(sizeof(int)*n);int i0;preorder(root,a,i);return a;
} 思路 1.首先题目要求放到malloced的数组里那就要考虑大小的问题最后还是运用TreeSize来求一下树里元素的数量比较好求出来后直接赋值给*returnsize 2.一般使用递归但是我们已经在函数里面动态开辟了递归每次调用会消耗很多最好的办法还是在构建一个函数来进行前置遍历和放入的操作。 3.考虑到参数设置问题root要有数组a也要有。那想到需要一个下标才能确保递归时正确放到位置这个下标还不能在递归函数里面定义那样没用都是新的独立的变量。 所以要作为参数传入的同时还能保证递归时改变的都是同一个变量那就有两种方法 全局变量传入地址地址虽然也是临时拷贝但是都是指向同一块区域
