网站改版需要注意什么,网站做SEO优化多少钱,园林景观设计公司名字,稻香村网站建设一、找树左下角的值
1.题目
Leetcode#xff1a;第 513 题
给定一个二叉树的 根节点 root#xff0c;请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3]
输出: 1示例 2: 输入: [1,2,3,4,null,5,6,null,null,7]
输出:…一、找树左下角的值
1.题目
Leetcode第 513 题
给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3]
输出: 1示例 2: 输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
2.解题思路
使用队列来实现层序遍历每次从队列中取出所有节点并检查每个节点的子节点将它们加入队列中以便后续遍历。在每一层中第一个被取出的节点即队列中的第一个节点将是该层的最左侧节点因此将其值设置为结果。当遍历结束时返回结果变量它包含了二叉树最底层的左侧值。
3.实现代码
#include iostream
#include vector
#include queue
using namespace std;// 定义一个结构体TreeNode用于表示二叉树的节点。
struct TreeNode {int val; // 存储节点的值。TreeNode* left; // 指向该节点左子树的指针。TreeNode* right; // 指向该节点右子树的指针。// TreeNode的构造函数用于创建一个TreeNode实例。// 参数x是节点的值left和right默认为NULL表示没有左右子节点。TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 一、找树左下角的值递归法
class Solution1 {
public:int maxDepth INT_MIN;// 初始化最大深度为最小整数值用于记录遍历过程中的最大深度。int result; // 初始化结果变量用于存储最底层左侧的值。// traversal函数用于递归遍历二叉树并找到最底层左侧的值。void traversal(TreeNode* root, int depth) {// 如果当前节点是叶子节点没有左右子节点检查当前深度是否大于已知的最大深度。if (root-left NULL root-right NULL) {if (depth maxDepth) { // 如果当前深度大于最大深度则更新最大深度并记录当前节点的值作为结果。maxDepth depth;result root-val;}return;// 到达叶子节点后返回不再继续遍历。}if (root-left) {// 如果当前节点有左子节点递归遍历左子树并在遍历完后减去深度。depth;traversal(root-left, depth);depth--;}if (root-right) {// 如果当前节点有右子节点递归遍历右子树并在遍历完后减去深度。depth;traversal(root-right, depth);depth--;}return;// 遍历过程中返回以便继续遍历其他分支。}// findBottomLeftValue函数是公共成员函数用于返回二叉树最底层左侧的值。int findBottomLeftValue(TreeNode* root) {traversal(root, 0);// 调用递归遍历函数遍历二叉树。return result; // 返回记录的最底层左侧的值。}
};// 二、找树左下角的值迭代法
class Solution2 {
public:// findBottomLeftValue函数用于找到并返回二叉树最底层的左侧值。int findBottomLeftValue(TreeNode* root) {queueTreeNode* que; // 创建一个队列que用于存储待遍历的节点。if (root ! NULL) que.push(root); // 如果根节点不为空将其入队。int result 0; // 初始化结果变量为0。// 使用while循环遍历队列不为空时的所有节点。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;// 返回记录的最底层左侧的值。}
};//测试
// 辅助函数用于创建一个新的TreeNode
TreeNode* createNode(int value) {return new TreeNode(value);
}// 辅助函数用于构建二叉树
TreeNode* buildTree(vectorint values) {if (values.empty()) return NULL;TreeNode* root createNode(values[0]);queueTreeNode* queueNode;queueNode.push(root);int i 1;while (!queueNode.empty()) {TreeNode* node queueNode.front();queueNode.pop();if (i values.size()) {node-left createNode(values[i]);queueNode.push(node-left);}if (i values.size()) {node-right createNode(values[i]);queueNode.push(node-right);}}return root;
}// 打印容器中的所有元素用于验证测试结果
void printVector(const vectorint vec) {for (int value : vec) {cout value ;}cout endl;
}// 主函数
int main() {vectorint treeValues { 1, 2, 3, 4, 5, 6, 7 };// 定义二叉树的层序遍历结果用于构建二叉树TreeNode* root buildTree(treeValues); // 构建二叉树Solution1 s1;// 创建Solution类的实例Solution2 s2;int result1 s1.findBottomLeftValue(root);// 传入二叉树的根节点int result2 s2.findBottomLeftValue(root);cout 二叉树的左下角的值递归法是: result1 endl;cout endl;cout 二叉树的左下角的值迭代法是: result2 endl;cout endl;return 0;
}二、路径总和
1.题目
Leetcode第 112 题
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。 示例 1 输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22
输出true
解释等于目标和的根节点到叶节点路径如上图所示。示例 2 输入root [1,2,3], targetSum 5
输出false
解释树中存在两条根节点到叶子节点的路径
(1 -- 2): 和为 3
(1 -- 3): 和为 4
不存在 sum 5 的根节点到叶子节点的路径。
示例 3
输入root [], targetSum 0
输出false
解释由于树是空的所以不存在根节点到叶子节点的路径
2.解题思路
使用递归法和迭代法遍历二叉树节点使用一个栈来存储每个节点及其对应的路径数值。在遍历过程中如果遇到叶子节点且其路径数值等于目标和返回true否则继续遍历左右子节点。如果遍历结束仍未找到满足条件的路径返回false。
3.实现代码
#include iostream
#include vector
#include stack
#include queue
using namespace std;// 定义一个结构体TreeNode用于表示二叉树的节点。
struct TreeNode {int val; // 存储节点的值。TreeNode* left; // 指向该节点左子树的指针。TreeNode* right; // 指向该节点右子树的指针。// TreeNode的构造函数用于创建一个TreeNode实例。// 参数x是节点的值left和right默认为NULL表示没有左右子节点。TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 一、二叉树的路径总和递归法
class Solution1 {
public:// traversal是一个辅助函数用于递归遍历二叉树检查是否存在路径和等于count的路径。// node是当前遍历到的节点count是当前的路径和与目标和的差值。bool traversal(TreeNode* node, int count) {// 如果当前节点是叶子节点并且count不等于0说明路径和不等于目标和返回false。if (node-left NULL node-right NULL count ! 0) return false;// 如果当前节点是叶子节点并且count等于0说明路径和等于目标和返回true。if (node-left NULL node-right NULL count 0) return true;// 如果当前节点有左子节点递归遍历左子树。if (node-left) {count - node-left-val; // 从当前路径和中减去左子节点的值因为左子节点的值是路径和的一部分。if (traversal(node-left, count)) return true; // 如果在左子树中找到满足条件的路径返回true。count node-left-val; // 回溯将左子节点的值加回到路径和中。}// 如果当前节点有右子节点递归遍历右子树。if (node-right) {count - node-right-val; // 从当前路径和中减去右子节点的值因为右子节点的值是路径和的一部分。if (traversal(node-right, count)) return true;// 如果在右子树中找到满足条件的路径返回true。count node-right-val; // 回溯将右子节点的值加回到路径和中。}return false;// 如果遍历完左右子树都没有找到满足条件的路径返回false。}// hasPathSum是一个成员函数用于判断是否存在从根节点到叶子节点的路径和等于目标和的路径。// root是二叉树的根节点targetSum是目标和。bool hasPathSum(TreeNode* root, int targetSum) {if (root NULL) return false;// 如果根节点为空返回false因为不存在路径。// 调用辅助函数traversal从根节点开始遍历初始路径和为targetSum - 根节点的值。return traversal(root, targetSum - root-val);}
};// 二、二叉树的路径总和迭代法
class Solution2 {
public:// haspathsum函数用于判断是否存在路径和等于sum的路径。// root是二叉树的根节点sum是目标和。bool haspathsum(TreeNode* root, int sum) {if (root NULL) return false;// 如果根节点为空返回false因为不存在路径。stackpairTreeNode*, int st;// 创建一个栈st用于存储节点指针和对应的路径数值。st.push(pairTreeNode*, int(root, root-val));// 将根节点及其路径数值根节点的值入栈。// 使用while循环遍历栈不为空时的所有元素。while (!st.empty()) {pairTreeNode*, int node st.top();// 取出栈顶元素包含节点指针和路径数值。st.pop();// 如果当前节点是叶子节点并且路径数值等于sum返回true。if (!node.first-left !node.first-right sum node.second) return true;// 如果当前节点有右子节点将其及其路径数值当前路径数值加上右子节点的值入栈。if (node.first-right) {st.push(pairTreeNode*, int(node.first-right, node.second node.first-right-val));}// 如果当前节点有左子节点将其及其路径数值当前路径数值加上左子节点的值入栈。if (node.first-left) {st.push(pairTreeNode*, int(node.first-left, node.second node.first-left-val));}}return false; // 如果遍历完所有节点都没有找到满足条件的路径返回false。}
};//测试
// 辅助函数用于创建一个新的TreeNode
TreeNode* createNode(int value) {return new TreeNode(value);
}// 辅助函数用于构建二叉树
TreeNode* buildTree(vectorint values) {if (values.empty()) return NULL;TreeNode* root createNode(values[0]);queueTreeNode* queueNode;queueNode.push(root);int i 1;while (!queueNode.empty()) {TreeNode* node queueNode.front();queueNode.pop();if (i values.size()) {node-left createNode(values[i]);queueNode.push(node-left);}if (i values.size()) {node-right createNode(values[i]);queueNode.push(node-right);}}return root;
}// 打印容器中的所有元素用于验证测试结果
void printVector(const vectorint vec) {for (int value : vec) {cout value ;}cout endl;
}// 主函数
int main() {vectorint treeValues { 1, 2, 3, 4, 5, 6, 7 };// 定义二叉树的层序遍历结果用于构建二叉树TreeNode* root buildTree(treeValues); // 构建二叉树Solution1 s1;// 创建Solution类的实例Solution2 s2;int targetSum 11;int result1 s1.hasPathSum(root, targetSum);// 传入二叉树的根节点int result2 s2.haspathsum(root, targetSum);cout targetSum targetSum endl;cout endl;cout 判断二叉树的路径总和递归法结果是: result1 endl;cout endl;cout 判断二叉树的路径总和迭代法结果是 result2 endl;cout endl;return 0;
}三、从中序与后序遍历序列构造二叉树
1.题目
Leetcode第 106 题
给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 示例 1: 输入inorder [9,3,15,20,7], postorder [9,15,7,20,3]
输出[3,9,20,null,null,15,7]示例 2:
输入inorder [-1], postorder [-1]
输出[-1]
2.解题思路
创建traversal函数递归地根据中序和后序遍历序列重建二叉树。首先确定根节点然后根据根节点在中序遍历序列中的位置分割序列得到左右子树的遍历序列。接着递归地重建左右子树并将它们分别作为根节点的左右子节点。buildTree函数是重建二叉树的入口点它调用traversal函数并传入中序和后序遍历序列。
3.实现代码
#include iostream
#include vector
#include queue
using namespace std;// 定义一个结构体TreeNode用于表示二叉树的节点。
struct TreeNode {int val; // 存储节点的值。TreeNode* left; // 指向该节点左子树的指针。TreeNode* right; // 指向该节点右子树的指针。// TreeNode的构造函数用于创建一个TreeNode实例。// 参数x是节点的值left和right默认为NULL表示没有左右子节点。TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 从中序与后序遍历序列构造二叉树
class Solution {
private:// traversal函数是一个辅助函数用于递归地重建二叉树。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 delimiterIndex;for (delimiterIndex 0; delimiterIndex inorder.size(); delimiterIndex) {if (inorder[delimiterIndex] rootValue) break;}// 根据根节点的位置分割中序遍历序列为左右子树的中序遍历序列。vectorint leftInorder(inorder.begin(), inorder.begin() delimiterIndex);vectorint rightInorder(inorder.begin() delimiterIndex 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;// 返回重建的根节点。}
public:// buildTree函数是公共成员函数用于根据给定的中序和后序遍历序列重建二叉树。TreeNode* buildTree(vectorint inorder, vectorint postorder) {if (inorder.size() 0 || postorder.size() 0) return NULL; // 如果中序或后序遍历序列为空返回空指针。return traversal(inorder, postorder);// 调用辅助函数开始重建二叉树。}
};//测试
// 辅助函数用于创建一个新的TreeNode
TreeNode* createNode(int value) {return new TreeNode(value);
}// 辅助函数用于构建二叉树
TreeNode* buildTree(vectorint values) {if (values.empty()) return NULL;TreeNode* root createNode(values[0]);queueTreeNode* queueNode;queueNode.push(root);int i 1;while (!queueNode.empty()) {TreeNode* node queueNode.front();queueNode.pop();if (i values.size()) {node-left createNode(values[i]);queueNode.push(node-left);}if (i values.size()) {node-right createNode(values[i]);queueNode.push(node-right);}}return root;
}// 打印容器中的所有元素用于验证测试结果
void printVector(const vectorint vec) {for (int value : vec) {cout value ;}cout endl;
}
int main()
{Solution s;vectorint inorder { 9,3,15,20,7 };vectorint postorder { 9,15,7,20,3 };TreeNode* results.buildTree(inorder, postorder);cout 从中序与后序遍历序列构造二叉树: endl;cout root result-val endl;cout root-left result-left-val endl;cout root-right result-right-val endl;cout root-right-left result-right-left-val endl;cout root-right-right result-right-right-val endl;return 0;
}ps以上皆是本人在探索算法旅途中的浅薄见解诚挚地希望得到各位的宝贵意见与悉心指导若有不足或谬误之处还请多多指教。
