代码随机化算法训练营第 15 天|第 15 天 二叉树
找树左下角的值
思路
咋眼一看,这道题目用递归的话就就一直向左遍历,最后一个就是答案呗?
没有这么简单,一直向左遍历到最后一个,它未必是最后一行啊。
我们来分析一下题目:在树的最后一行找到最左边的值。
首先要是最后一行,然后是最左边的值。
如果使用递归法,如何判断是最后一行呢,其实就是深度最大的叶子节点一定是最后一行。
所以要找深度最大的叶子节点。
那么如何找最左边的呢?可以使用前序遍历(当然中序,后序都可以,因为本题没有 中间节点的处理逻辑,只要左优先就行),保证优先左边搜索,然后记录深度最大的叶子节点,此时就是树的最后一行最左边的值。
递归三部曲:
确定递归函数的参数和返回值
参数必须有要遍历的树的根节点,还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了,所以递归函数的返回类型为void。
本题还需要类里的两个全局变量,maxLen用来记录最大深度,result记录最大深度最左节点的数值。
int maxDepth = -1;
int bottomLeftValue;
void dfs(struct TreeNode* node, int depth) {
if (node == NULL) return;
if (depth > maxDepth) {
maxDepth = depth;
bottomLeftValue = node->val;
}
dfs(node->left, depth + 1);
dfs(node->right, depth + 1);
}
int findBottomLeftValue(struct TreeNode* root) {
dfs(root, 0);
return bottomLeftValue;
}
学习反思
刚开始没想到一直向左遍历到最后一个,它未必是最后一行。
路径总和
题目链接/文章讲解/视频讲解:https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html
思路
1.递归
bool hasPathSum(struct TreeNode* root, int targetSum){
if(!root)
return false;
if(!root->right && !root->left && targetSum == root->val)
return true;
return hasPathSum(root->right, targetSum - root->val) || hasPathSum(root->left, targetSum - root->val);
}
2.迭代
struct Pair {
struct TreeNode* node;
int sum;
};
bool hasPathSum(struct TreeNode* root, int targetSum){
struct Pair stack[1000];
int stackTop = 0;
if(root) {
struct Pair newPair = {root, root->val};
stack[stackTop++] = newPair;
}
while(stackTop) {
struct Pair topPair = stack[--stackTop];
if(!topPair.node->left && !topPair.node->right && topPair.sum == targetSum)
return true;
if(topPair.node->left) {
struct Pair newPair = {topPair.node->left, topPair.sum + topPair.node->left->val};
stack[stackTop++] = newPair;
}
if(topPair.node->right) {
struct Pair newPair = {topPair.node->right, topPair.sum + topPair.node->right->val};
stack[stackTop++] = newPair;
}
}
return false;
}
学习反思
对二叉树有更多的理解。
从中序与后序遍历序列构造二叉树
题目链接/文章讲解/视频讲解:https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html
思路
首先回忆一下如何根据两个顺序构造一个唯一的二叉树,相信理论知识大家应该都清楚,就是以 后序数组的最后一个元素为切割点,先切中序数组,根据中序数组,反过来再切后序数组。一层一层切下去,每次后序数组最后一个元素就是节点元素。
说到一层一层切割,就应该想到了递归。
来看一下一共分几步:
-
第一步:如果数组大小为零的话,说明是空节点了。
-
第二步:如果不为空,那么取后序数组最后一个元素作为节点元素。
-
第三步:找到后序数组最后一个元素在中序数组的位置,作为切割点
-
第四步:切割中序数组,切成中序左数组和中序右数组 (顺序别搞反了,一定是先切中序数组)
-
第五步:切割后序数组,切成后序左数组和后序右数组
-
第六步:递归处理左区间和右区间
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
if(!preorderSize)
return NULL;
int rootValue = preorder[0];
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = rootValue;
root->left = NULL;
root->right = NULL;
if(preorderSize == 1)
return root;
int index;
for(index = 0; index < inorderSize; index++) {
if(inorder[index] == rootValue)
break;
}
int leftNum = index;
int rightNum = inorderSize - index - 1;
int* leftInorder = inorder;
int* rightInorder = inorder + leftNum + 1;
int* leftPreorder = preorder+1;
int* rightPreorder = preorder + 1 + leftNum;
root->left = buildTree(leftPreorder, leftNum, leftInorder, leftNum);
root->right = buildTree(rightPreorder, rightNum, rightInorder, rightNum);
return root;
}
int linearSearch(int* arr, int arrSize, int key) {
int i;
for(i = 0; i < arrSize; i++) {
if(arr[i] == key)
return i;
}
return -1;
}
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
if(!inorderSize)
return NULL;
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = postorder[postorderSize - 1];
int index = linearSearch(inorder, inorderSize, postorder[postorderSize - 1]);
int rightSize = inorderSize - index - 1;
node->left = buildTree(inorder, index, postorder, index);
node->right = buildTree(inorder + index + 1, rightSize, postorder + index, rightSize);
return node;
}
学习反思
对二叉树有更多的理解。
总结
今天的题目相对来说还是比较基础,加油!!!
下一篇: Artalk 多站点评论系统的部署和使用
推荐阅读
-
Python 第 7 和第 8 次作业
-
代码随机化算法训练营第 15 天|第 15 天 二叉树
-
Java 游戏超级马里奥 - II 代码编写
-
Java 项目实践 II 基于 Java + Spring Boot + MySQL 的匹配网站设计与实施(源代码 + 数据库 + 文档)
-
JavaScript 第 16 章:错误处理和调试
-
[算法] 动态程序设计类 (2) - 01 背包 + 完整背包(注释)
-
香港 NEXT 如何使用 @Styles 装饰器优化组件代码?-第 1 步:定义全局 @Styles 方法
-
53.寻宝游戏(CardCode.com 第 7 次模拟笔试)
-
Humboldt NEXT 如何使用 @Styles 装饰器优化组件代码?
-
[AcWing]基础算法课程--数据结构