做网站(信科网络),服装网站建设公司有哪些,wordpress爆破字典,百度怎么发布网站LeetCode 104.二叉树的最大深度
1. 题目描述#xff1a; 给定一个二叉树 root #xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;3示例…LeetCode 104.二叉树的最大深度
1. 题目描述 给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1 输入root [3,9,20,null,null,15,7]
输出3示例 2 输入root [1,null,2]
输出2提示 树中节点的数量在 [0, 104] 区间内。-100 Node.val 100 OJ题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2. 整体思路
首先要判断根是否存在如果根存在继续向下遍历再次遍历的时候先判断其左右子树是否存在若存在再遍历其左右子树此时就不用再进行根判断了根判断的代码只在进入函数时有效执行。 以下是我们的大致思路但是递归的图着实太难画了实在不理解可以仔细参照文字或者自己画
在画图的过程中我们也发现了我们每次都要返回左右子树遍历后的较大值如何做 这时我们可以借用C语言库中的较大值函数而且可以进行代码的简化 3.解题代码
int maxDepth(struct TreeNode* root)
{if (root NULL){return 0;}return fmax(maxDepth(root-left), maxDepth(root-right)) 1;
}
LeetCode 100.相同的树
1.题目描述 给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 示例 1 输入p [1,2,3], q [1,2,3]
输出true示例 2 输入p [1,2], q [1,null,2]
输出false示例 3 输入p [1,2,1], q [1,1,2]
输出false提示 两棵树上的节点数目都在范围 [0, 100] 内-104 Node.val 104 OJ题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2.整体思路
我们先比较根然后比较左子树再比较右子树。 比较根时我们要注意根的情况如果两根都为空或者某一根为空 当过筛后我们才能进行递归。
3.解题代码
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);}
LeetCode 965.单值二叉树
1.题目描述 如果二叉树每个节点都具有相同的值那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时才返回 true否则返回 false。 示例 1 输入[1,1,1,1,1,null,1]
输出true示例 2 输入[2,2,2,5,2]
输出false提示 给定树的节点数范围是 [1, 100]。每个节点的值都是整数范围为 [0, 99] 。 OJ题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
2.整体思路
我们可以考虑如何使用递归来解题首先要考虑的肯定是父子结点的关系我们把每棵树都分为根、左结点、右结点在刚开始比较三者的值若相等就继续向下递归。然后我们根据思路还加以改进判断了根的左右结点是否存在后写了以下代码 我们运行时测试用例正确但提交时却报错 原来是我们加以判断的左右子树是否存在的条件忽略了只存在一个结点且与根不一样的情况
我们改进了代码现在只有当子结点存在且与根结点的值相等时才会进行递归。
3.解题代码 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;bool leftans isUnivalTree(root-left);bool rightans isUnivalTree(root-right);return leftans rightans;}
LeetCode 144.二叉树的前序遍历
1.题目描述 给你二叉树的根节点 root 返回它节点值的 前序 遍历。 示例 1 输入root [1,null,2,3]
输出[1,2,3]示例 2 输入root []
输出[]示例 3 输入root [1]
输出[1]示例 4 输入root [1,2]
输出[1,2]示例 5 输入root [1,null,2]
输出[1,2]提示 树中节点数目在范围 [0, 100] 内-100 Node.val 100 2.整体思路
我们先来看他代码区的代码其实还是能发现一点端倪的这和我们之前写的前序遍历大不相同这道OJ题需要一个返回值他要求我们放到数组里面。 然而数组应该开多大呢returnSize其实并非是题者给我们的提示所以我们需要遍历二叉树自己找到二叉树的结点个数这就用到了二叉树中求结点个数的函数 然后我们看到returnSize我们先来解释一下啊returnSize的意思它并不是题者给我们的提示在LeetCode中当需要我们malloc来返回数组时通常参数都会给我们配returnSize在我们的代码中我们需要修改returnSize的值以此让OJ后台能遍历我们的数组。
我们来写一个把值存放入数组的前序遍历函数其实和前序遍历的区别就是不打印而存入数组。
最后在我们的主函数中我们只需要调用上述函数并将存入数组的下标传入即可
3.解题代码
int TreeSize(struct TreeNode* root)
{if(root NULL)return 0;return TreeSize(root-left) TreeSize(root-right) 1;
}
void Preorder(struct TreeNode* root, int* a, int* p)
{if(root NULL)return;a[*p] root-val;(*p);Preorder(root-left, a, p);Preorder(root-right, a, p);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{int size TreeSize(root);int* a (int*)malloc(sizeof(int) * size);*returnSize size;int i 0;Preorder(root, a, i);return a;
}
