行业知识
@[TOC](代码随想录算法训练营第十八天|Leetcode513 找树左下角的值、Leetcode112 路径总和、Leetcode106 从中序与后序遍历序列构造二叉树
代码随想录算法训练营第十八天|Leetcode513 找树左下角的值、Leetcode112 路径总和 113 路径总和ii、Leetcode106 从中序与后序遍历序列构造二叉树 105 从前序与中序遍历序列构造二叉树
- ● Leetcode513 找树左下角的值
- ● 解题思路
- ● 代码实现
- ● Leetcode112 路径总和
- ● 解题思路
- ● 代码实现
- ● 相关题目：Leetcode113 路径总和ii
- ● 解题思路
- ● 代码实现
- ● Leetcode106 从中序与后序遍历序列构造二叉树
- ● 使用数组元素构建二叉树
- ● 解题思路
- ● 代码实现
- ● 相关题目：Leetcode105 从前序与中序遍历序列构造二叉树
- ● 代���实现
● Leetcode513 找树左下角的值
题目链接：Leetcode513 找树左下角的值
视频讲解：代码随想录|找树左下角的值
题目描述：给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
● 解题思路
方法一：递归
（1）确定递归函数的参数和返回值：
我们定义了result的全局变量存储最终结果，因此在traversal遍历过程直接对其更改即可，不需要其他返回值，因此在traversal返回值为void，同时需要传入递归的结点和递归时传入结点的深度；
（2）确定递归终止条件：
我们需要得到的是左下角的值，显然左下角的值不管是上一层结点的左孩子或者右孩子，都一定会是叶子结点，同时我们需要对其深度进行判断，因此左下角的值一定处于二叉树的最后一层，即深度最大；
（3）确定单层遍历逻辑：
因为我们需要得到左下角的结点，因此和中结点的处理没有关系，所以无论哪种遍历都可以实现。
需要再次注意，左下角的值不一定是左结点，当倒数第二层最左侧结点只有右孩子而没有左孩子，此时其右孩子将会是最左结点；同时注意每一次递归都需要对应一次回溯。
方法二：迭代
本题使用层序遍历进行迭代解决更简单，我们将最后一层的队头元素返回即可。
● 代码实现
方法一：递归
/** * 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 maxDepth = INT_MIN;//存储最大深度 int result; void traversal(TreeNode* node, int depth) { //终止条件 if(!node->left && !node->right) { if(depth > maxDepth) { maxDepth = 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; }};当我们将回溯隐藏精简之后得到：
/** * 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 maxDepth = INT_MIN; int result; void traversal(TreeNode* node, int depth) { //终止条件 if(!node->left && !node->right) { if(depth > maxDepth) { maxDepth = depth; result = node->val; } return; } //左 if(node->left) { traversal(node->left, depth + 1); } //右 if(node->right) { traversal(node->right, depth + 1); } } int findBottomLeftValue(TreeNode* root) { traversal(root, 0); return result; }};这里注意不能depth++，如果自加操作后就改变了depth的值，无法完成回溯操作。
方法二：迭代
/** * 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 que; int result = 0; if(!root) return result; que.push(root); while(!que.empty()) { int size = que.size(); result = que.front()->val; for(int i = 0; i left) que.push(node->left); if(node->right) que.push(node->right); } } return result; }};● Leetcode112 路径总和
题目链接：Leetcode112 路径总和
视频讲解：代码随想录|路径总和
题目描述：给你二叉树的根节点 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
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
● 解题思路
方法一：迭代
（1）确定递归函数参数和返回值：
我们只需要判断某条路径是否结点值相加总和是否等于target，因此返回值为bool，传入参数为node和target即可；
（2）确定函数的终止条件：
在遍历过程中，我们会在某条路径上遇到两种可能，第一种是到叶子结点时，整个路径值相加不等于target，将其返回false；另一种就是等于target，将true的结果返回给上一层告诉该路径有满足条件；
（3）确定单层遍历逻辑：
在整个遍历过程中，我们不需要对中进行任何处理，只需要遍历左右结点的路径上是否有满足==target的情况，因此无论使用哪种遍历顺序都是可以的。
同时，当左右结点有满足：if(traversal(node->left/right, target - node->left/right- >val))，就需要返回true;
方法二：迭代
迭代法解决本题主要需要借助栈，但栈中的元素需要使用pari，其中int存储的值为从根结点到该结点路径的总和，思路理解确实不难，但在向栈中压入元素时注意first和second，脑子不乱但手可能乱。
● 代码实现
方法一：迭代
/** * 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 traversal(TreeNode* node, int targetSum) { //终止条件 if(!node->left && !node->right && targetSum == 0) return true; if(!node->left && !node->right) return false; //左 if(node->left) { targetSum -= node->left->val; if(traversal(node->left, targetSum)) return true; targetSum += node->left->val; } //右 if(node->right) { targetSum -= node->right->val; if(traversal(node->right, targetSum)) return true; targetSum += node->right->val; } return false; } bool hasPathSum(TreeNode* root, int targetSum) { if(!root) return false; return traversal(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 traversal(TreeNode* node, int count) { //终止条件 if(!node->left && !node->right && count == 0) return true; if(!node->left && !node->right) return false; //左 if(node->left && traversal(node->left, count - node->left->val)) return true; //右 if(node->right && traversal(node->right, count - node->right->val)) return true; return false; } bool hasPathSum(TreeNode* root, int targetSum) { if(!root) return false; return traversal(root, targetSum - root->val); }};最终精简为：
class Solution {public: bool hasPathSum(TreeNode* root, int sum) { if (!root) return false; if (!root->left && !root->right && sum == root->val) { return true; } return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - 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) return false; stack st; st.push(pair(root, root->val)); while(!st.empty()) { pair node = st.top(); st.pop(); if(!node.first->left && !node.first->right && node.second == targetSum) return true; if(node.first->right) { st.push(pair(node.first->right, node.second + node.first->right->val)); } if(node.first->left) { st.push(pair(node.first->left, node.second + node.first->left->val)); } } return false; }};● 相关题目：Leetcode113 路径总和ii
题目链接：Leetcode113 路径总和ii
题目描述：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
● 解题思路
本题整体思路和返回true or false相同，但在结果需要返回满足要求的所有路径，我们使用两个vector，一个存储遍历的路径，一个将满足条件的路径保存在result中，最后输出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: vector result; vector path; void traversal(TreeNode* node, int count) { //终止条件 if(!node->left && !node->right && count == 0) { result.push_back(path); 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; } vector pathSum(TreeNode* root, int targetSum) { result.clear(); path.clear(); if(!root) return result; path.push_back(root->val); traversal(root, targetSum - root->val); return result; }};● Leetcode106 从中序与后序遍历序列构造二叉树
题目链接：Leetcode106 从中序与后序遍历序列构造二叉树
视频讲解：代码随想录|从中序与后序遍历序列构造二叉树
题目描述：给定两个整数数组 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]
提示:
1 public: TreeNode* traversal(vector //·当数组大小为0，返回nullptr if(postorder.size() == 0) return nullptr; //·当数组不为空，后序结果的最后一个值为根结点 int rootValue = postorder[postorder.size() - 1]; TreeNode* root = new TreeNode(rootValue); //·找到后序数组最后一个元素在中序数组的位置，作为切割点 int index; for(index = 0; index
● 相关题目：Leetcode105 从前序与中序遍历序列构造二叉树
题目链接：Leetcode105 从前序与中序遍历序列构造二叉树
题目描述：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
● 代码实现
/** * 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& preorder, int preorderBegin, int preorderEnd, vector& inorder, int inorderBegin, int inorderEnd) { if(preorderBegin == preorderEnd) return nullptr; int rootValue = preorder[preorderBegin]; TreeNode* root = new TreeNode(rootValue); if(preorderEnd - preorderBegin == 1) return root; int index; for(index = 0; index left = traversal(preorder, leftpreorderBegin, leftpreorderEnd ,inorder, leftinorderBegin, leftinorderEnd); root->right = traversal(preorder, rightpreorderBegin, rightpreorderEnd, inorder, rightinorderBegin, rightinorderEnd); return root; } TreeNode* buildTree(vector& preorder, vector& inorder) { if(preorder.size() == 0 || inorder.size() == 0) return nullptr; return traversal(preorder, 0, preorder.size(), inorder, 0, inorder.size()); }};
- ● 代���实现
上一篇：戴尔服务器怎么装普通系统?
