临沂企业建站效果好,河间市网站建设公司,搭建网站的英语,做移动网站优化软件刷题的第十五天#xff0c;希望自己能够不断坚持下去#xff0c;迎来蜕变。#x1f600;#x1f600;#x1f600; 刷题语言#xff1a;C Day15 任务 ● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历…刷题的第十五天希望自己能够不断坚持下去迎来蜕变。 刷题语言C Day15 任务 ● 513.找树左下角的值 ● 112. 路径总和 113.路径总和ii ● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
1 找树左下角的值 本题要找出树的最后一行最左边的值 思路1层序遍历 思路2递归
迭代法 层序遍历模板参考代码随想录刷题题Day12
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queueTreeNode* que;int result;if (root ! NULL) que.push(root);while (!que.empty()){int size que.size();for (int i 0; i size; i){TreeNode* node que.front();que.pop();if (i 0) result node-val;// 记录最后一行第一个元素if (node-left) que.push(node-left);if (node-right) que.push(node-right);}}return result;}
};递归法 误区不是一直向左遍历最后一个就是答案 一直向左遍历到最后一个未必是最后一行 关键在树的最后一行找到最左边的值 (1) 判断最后一行深度最大的叶子节点 (2) 最左边的值可以使用前序遍历当然中序后序都可以因为本题没有 中间节点的处理逻辑只要左优先就行保证优先左边搜索然后记录深度最大的叶子节点此时就是树的最后一行最左边的值。 1确定递归函数的参数和返回值 参数要遍历的树的根节点最长深度 返回值void
int maxDepth INT_MIN;// 全局变量 记录最大深度
int result; // 全局变量 最大深度最左节点的数值
void traversal(TreeNode* node, int depth)2确定终止条件 当遇到叶子节点的时候就需要统计一下最大的深度了所以需要遇到叶子节点来更新最大深度。 if (node-left NULL node-right NULL)
{if (depth maxDepth){maxDepth depth; // 更新最大深度result node-val; // 最大深度最左面的数值}return;
}3确定单层递归的逻辑 找最大深度的时候递归的过程中依然要使用回溯 // 中
if (node-left) {// 左depth;// 深度加一traversal(node-left, depth);depth--;// 回溯深度减一
}
if (node-right) {// 右depth;// 深度加一traversal(node-right, depth);depth--;// 回溯深度减一
}C
class Solution {
public:int maxDepth INT_MIN;int result;void traversal(TreeNode* node, int depth) {if (node-left NULL node-right NULL) {if (maxDepth depth) {maxDepth depth;result node-val;}}if (node-left) {depth;traversal(node-left, depth);depth--;}if (node-right) {depth;traversal(node-right, depth);depth--;}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};精简版本C
class Solution {
public:int maxDepth INT_MIN;int result;void traversal(TreeNode* node, int depth) {if (node-left NULL node-right NULL) {if (maxDepth depth) {maxDepth depth;result node-val;}}if (node-left) {traversal(node-left, depth 1);// 隐藏着回溯}if (node-right) {traversal(node-right, depth 1);// 隐藏着回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};2 路径总和 思路 使用深度优先遍历的方式本题前中后序都可以因为中间节点没有处理逻辑 递归法 1确定递归函数的参数和返回类型 参数二叉树的根节点、计算器用来计算二叉树的一条边之和是否正好是目标和 返回值要找一条符合条件的路径所以递归函数需要返回值遍历的路线并不要遍历整棵树及时返回返回类型是bool 递归函数返回值 1如果需要搜索整棵二叉树且不用处理递归返回值递归函数就不要返回值 2如果需要搜索整棵二叉树且需要处理递归返回值递归函数就需要返回值。 3如果要搜索其中一条符合条件的路径那么递归一定需要返回值因为遇到符合条件的路径了就要及时返回 bool traversal(TreeNode* node, int count)2确定终止条件 计数器count初始为目标和然后每次减去遍历路径节点上的数值 如果最后count 0同时到了叶子节点的话说明找到了目标和如果遍历到了叶子节点count不为0就是没找到
if (node-left NULL node-right NULL count 0) return true;
if (node-left NULL node-right NULL count ! 0) return false;3确定单层递归的逻辑 递归函数是有返回值的如果递归函数返回true说明找到了合适的路径应该立刻返回 if (node-left) {// 左 空节点不遍历// 遇到叶子节点返回true则直接返回trueif (traversal(node-left, count - node-left-val)) return true;
}
if (node-right) {// 右 空节点不遍历// 遇到叶子节点返回true则直接返回trueif (traversal(node-right, count - node-right-val)) return true;
return false;把回溯的过程表现出来
if (node-left) {// 左count - node-left-val;// 递归处理节点;if (traversal(node-left, count)) return true;count node-left-val;// 回溯撤销处理结果
}
if (node-right) { // 右count - node-right-val;if (traversal(node-right, count)) return true;count node-right-val;// 回溯撤销处理结果
}C
class Solution {
public:bool traversal(TreeNode* node, int count) {if (node-left NULL node-right NULL count 0) return true;// 遇到叶子节点并且计数为0if (node-left NULL node-right NULL count ! 0) return false;// 遇到叶子节点直接返回if (node-left) {// 左count - node-left-val;// 递归处理节点;if (traversal(node-left, count)) return true;count node-left-val;// 回溯撤销处理结果}if (node-right) {// 右count - node-right-val;// 递归处理节点if (traversal(node-right, count)) return true;count node-right-val;// 回溯撤销处理结果}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if (root NULL) return false;return traversal(root, targetSum - root-val);}
};精简版本C
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if (!root) return false;if (!root-left !root-right targetSum root-val) {return true;}return hasPathSum(root-left, targetSum - root-val) || hasPathSum(root-right, targetSum - root-val);}
};思路 路径总和ii要遍历整个树找到所有路径所以递归函数不要返回值
class Solution {
public:vectorvectorint result;vectorint path;// 递归函数不需要返回值因为我们要遍历整个树void traversal(TreeNode* node, int count) {if (node-left NULL node-right NULL count 0) {result.push_back(path);return;}if (node-left NULL node-right NULL) return;// 遇到叶子节点而没有找到合适的边直接返回if (node-left) {// 左 空节点不遍历path.push_back(node-left-val);count - node-left-val;traversal(node-left, count);// 递归count node-left-val;// 回溯path.pop_back();// 回溯}if (node-right) {// 右 空节点不遍历path.push_back(node-right-val);count - node-right-val;traversal(node-right, count);// 递归count node-right-val;// 回溯path.pop_back();// 回溯}return;}vectorvectorint pathSum(TreeNode* root, int targetSum) {result.clear();path.clear();if (root NULL) return result;path.push_back(root-val);// 把根节点放进路径traversal(root, targetSum - root-val);return result;}
};3 从中序与后序遍历序列构造二叉树 思路 后序数组为0空节点后序数组最后一个元素为节点元素寻找中序数组位置作为切割点切中序数组切后序数组递归处理左右区间 C
class Solution {
public:TreeNode* traversal(vectorint inorder, vectorint postorder) {if (postorder.size() 0) return NULL;// 后序遍历数组最后一个元素就是当前的中间节点int rootValue postorder[postorder.size() - 1];TreeNode* root new TreeNode(rootValue);// 叶子节点if (postorder.size() 1) return root;// 找到中序遍历的切割点int index;for (index 0; index inorder.size(); index){if (inorder[index] rootValue) break;}// 切割中序数组vectorint leftInorder(inorder.begin(), inorder.begin() index);vectorint rightInorder(inorder.begin() index 1, inorder.end());postorder.resize(postorder.size() - 1);// 切割后序数组vectorint leftPostorder(postorder.begin(), postorder.begin() leftInorder.size());vectorint rightPostorder(postorder.begin() leftInorder.size(), postorder.end());root-left traversal(leftInorder, leftPostorder);root-right traversal(rightInorder, rightPostorder);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {if (inorder.size() 0 || postorder.size() 0) return NULL;return traversal(inorder, postorder);}
};4 从前序与中序遍历序列构造二叉树 思路 前序数组为0空节点前序数组第一个元素为节点元素寻找中序数组位置作为切割点切中序数组切前序数组递归处理左右区间 C
class Solution {
public:TreeNode* traversal(vectorint preorder, vectorint inorder) {// 前序数组为0空节点if (preorder.size() 0) return NULL;// 前序数组第一个元素为节点元素int rootValue preorder[0];TreeNode* root new TreeNode(rootValue);if (preorder.size() 1) return root;// 寻找中序数组位置作为切割点int index;for (index 0; index inorder.size(); index) {if (inorder[index] rootValue) break;}// 切中序数组vectorint leftInorder(inorder.begin(), inorder.begin() index);vectorint rightInorder(inorder.begin() index 1, inorder.end());// 切前序数组preorder.erase(preorder.begin());vectorint leftPreorder(preorder.begin(), preorder.begin() leftInorder.size());vectorint rightPreorder(preorder.begin() leftPreorder.size(), preorder.end());// 递归处理左右区间root-left traversal(leftPreorder, leftInorder);root-right traversal(rightPreorder, rightInorder);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {if (preorder.size() 0 || inorder.size() 0) return NULL;return traversal(preorder, inorder);}
};鼓励坚持十六天的自己
