本文主要是介绍代码随想录算法训练营第十八天 |力扣513 找树左下角的值 力扣112 路径总和 力扣106 从中序与后序遍历序列构造二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
day18 记录代码随想录
第一题 力扣513 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
题目链接：力扣题目链接
迭代法比较简单：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*///迭代法
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;que.push(root);int result = 0;while(!que.empty()) {int size = que.size();result = que.front()->val;while(size--) {TreeNode* node = que.front();que.pop();if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return result;}
};迭代法也不难：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*///递归法-回溯
class Solution {
public:int result;int maxdep = -1; //naxdep = INT_MINvoid traversal(TreeNode* node, int depth) {if(node->left == NULL && node->right == NULL) {if( depth > maxdep) {maxdep = depth;result = node->val;}return;}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;}
};第二题 力扣112 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
题目链接：112. 路径总和
递归：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool findtarget(TreeNode* node, int count) {if(node->left == NULL && node->right == NULL) {return count == 0;}if(node->left) {count -= node->left->val;if(findtarget(node->left, count))return 1;count += node->left->val;}if(node->right) {count -= node->right->val;if(findtarget(node->right, count))return 1;count += node->right->val;}return 0;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == NULL) return 0;return findtarget(root, targetSum - root->val);}
};迭代：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*///迭代
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if (root == NULL) return 0;stack<pair<TreeNode*, int>> st;st.push(pair(root, root->val));while(!st.empty()) {pair<TreeNode*, int> node = st.top();st.pop();if(!node.first->left && !node.first->right && node.second == targetSum)return 1;if(node.first->left)st.push(pair(node.first->left, node.second + node.first->left->val));if(node.first->right)st.push(pair(node.first->right, node.second + node.first->right->val));}return 0;}
};第三题 力扣106 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
题目链接：力扣题目链接
分六步，代码如下：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* traversal(vector<int> &inorder, vector<int> &postorder) {//第一步：当数组为0时，则说明是空节点if(postorder.size() == 0) return NULL;//第二步：从后序找最后一个为中节点int mid = postorder[postorder.size()-1];TreeNode* root = new TreeNode(mid); //将中节点作为根节点//叶子节点if(postorder.size() == 1) return root;//第三部：从中序找分割点int index = 0;for (index = 0; index < inorder.size(); index++)if (inorder[index] == mid)break;//第四部：将中序分割为左数组和右数组vector<int> leftinorder(inorder.begin(), inorder.begin() + index);vector<int> rightinorder(inorder.begin() + index + 1, inorder.end());//第五步：将后序分割为左数组和右数组vector<int> leftpostorder(postorder.begin(), postorder.begin() + leftinorder.size());vector<int> rightpostorder(postorder.begin() + leftinorder.size(), postorder.end() - 1);//第六步：递归处理root->left = traversal(leftinorder, leftpostorder);root->right = traversal(rightinorder, rightpostorder);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {//if (postorder.size() == 0) return 0return traversal(inorder, postorder);}
};这篇关于代码随想录算法训练营第十八天 |力扣513 找树左下角的值 力扣112 路径总和 力扣106 从中序与后序遍历序列构造二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
