代码随想录算法训练营第十六天|513. 找树左下角的值 112. 路径总和 106. 从中序与后序遍历序列构造二叉树
513. 找树左下角的值
题目
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
题目解析---迭代法
层序遍历，然后只需要记录最后一行第一个节点的数值就可以了。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*>que;
if(root!=NULL)que.push(root);
int result=0;
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;
}
};112. 路径总和
题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
题目解析---递归法
这里使用深度优先遍历数组
递归三步走
确定参数和返回值
参数：需要二叉树的根节点，以及记录路径的数组path，以及传递target
确定终止条件
访问到叶子节点就终止，并且在此时进行比较，如果记录的路径和等于target，则返回true
确定单层递归的逻辑
因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
递归函数是有返回值的，如果左右只要有一个递归函数返回true，最后都返回true
class Solution {
public:
bool tranversal(TreeNode*root,vector<int>&path,int targetSum){
path.push_back(root->val);
if(root->left==NULL&&root->right==NULL){
int sum=0;
for(int i=0;i<path.size();i++){
sum+=path[i];
}
if(sum==targetSum)return true;
}
bool leftbool=false,rightbool=false;
if(root->left){
leftbool=tranversal(root->left,path,targetSum);
path.pop_back();
}
if(root->right){
rightbool=tranversal(root->right,path,targetSum);
path.pop_back();
}
return (leftbool||rightbool);
}
bool hasPathSum(TreeNode* root, int targetSum) {
vector<int>path;
if(root==NULL)return false;
return tranversal(root,path,targetSum);
}
};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]
题目解析
后序遍历的二叉树数组会有一个特点，所有根节点会在数组的最后，而中序遍历是先遍历左子树再根节点最后右子树。
所以这道题的解题思路就是首先从后序遍历数组取最后一个元素，然后找中序数组中该元素的位置，切割中序数组，此时该元素左边的所有元素值为根节点左子树的值，右边的元素为根节点右子树上的元素。后面不断递归，直到二叉树被构建好。
思路是这么个思路，然后代码实现里还有许多细节需要注意。下面就来说一说：
post_idx：从后向前遍历后序遍历数组
idx_map：<元素值，下标> 方便直接找到后序遍历中的元素值对应在中序遍历数组中的下标
在主函数里将这些定义好后就可以开始递归了
首先看看递归传的参数
一个左，一个右，然后还有两个vector。左右是用来确定子树的范围的，比如所给案例里，root结点的左子树的范围就是0，右子树是2-4。
终止条件
如果子树的范围被压缩得没有了，那么说明此时得这个节点是一个叶子结点，直接返回空就可以
单次递归逻辑
从后序数组里取出对应post_idx位置的元素，在中序数组里找到对应index，然后切割中序数组，左子树的根节点在左边找，右子树的根节点在右边找，然后返回当前节点。
C++代码：
class Solution {
int post_idx;
unordered_map<int,int>idx_map;
public:
TreeNode*helper(int leftindex,int rightindex,vector<int>& inorder, vector<int>& postorder){
if (leftindex > rightindex) {
return nullptr;
}
int root_val = postorder[post_idx];
TreeNode* root = new TreeNode(root_val);
int index=idx_map[root->val];
post_idx--;
root->right=helper(index+1,rightindex,inorder,postorder);
root->left=helper(leftindex,index-1,inorder,postorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
post_idx=inorder.size()-1;
int idx=0;
for(auto&val:inorder){
idx_map[val]=idx++;
}
return helper(0,inorder.size()-1,inorder,postorder);
}
};原文地址：https://blog.csdn.net/Ustianan/article/details/142895231
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！