代码随想录算法训练营43期 | Day 16—— 513. 找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树

代码随想录算法训练营43期 | Day 16

513. 找树左下角的值

class Solution {
public:int maxdepth = INT_MIN;int result;//确定递归函数的返回值和参数,根节点 和 深度deepth 找到叶子结点 比较深度void getVal(TreeNode* node, int deepth){//递归终止的条件if(node->left==nullptr&&node->right==nullptr){if(deepth>maxdepth){maxdepth = deepth;result = node->val;}return ;}//if(node->left){deepth++;getVal(node->left,deepth);deepth--;}if(node->right){deepth++;getVal(node->right,deepth);deepth--;}return ;}int findBottomLeftValue(TreeNode* root) {getVal(root,0);return result;}
};

层序遍历：

class Solution {
public:int findBottomLeftValue(TreeNode* root) {//层序遍历 返回最底层第一个节点//定义一个双向队列 queue<TreeNode*> que;if(root!=nullptr){que.push(root);}//用于保存最后结果int result;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. 路径总和

寻求二叉树中目标和，元素相加等于目标和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，

解题思路

1. 确定遍历顺序
2. 确定递归终止条件
3. 确定单层递归逻辑

遍历顺序：前序、中序、后序均可

//确定传入的参数和返回值,根节点、目标值,遇到节点，做减法
bool traversal(TreeNode* node,int count)
{//遇到叶子节点， 找到路径 返回trueif(node->left==nullptr&&node->right==nullptr&&count==0)return true;//遇到叶子节点，同时count不为0 返回falseif(node->left==nullptr&&node->right==nullptr&&node!=0) 		 return false; //左if(node->left) {count = count - node->left->value;if(traversal(node->left,count)){return true;count+=node->left->val;}
}//右if(node->right){count = count - node->right->value;if(traversal(node->right,count)) return true;count+= node->right->value;}return false;

广度优先搜索:

class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if(root == nullptr){return false;}//定义一个队列queue<TreeNode*> que_node;queue<int> que_val;//根节点入队que_node.push(root);que_val.push(root->val);//循环条件，队列不为空while(!que_node.empty()){TreeNode* cur = que_node.front();//获取队列中队头元素int temp  = que_val.front();//出队que_node.pop();que_val.pop();//判断返回条件if(cur->left==nullptr&&cur->right==nullptr){if(temp==targetSum){return true;}}//左if(cur->left){que_node.push(cur->left);que_val.push(cur->left->val + temp);}//右if(cur->right){que_node.push(cur->right);que_val.push(cur->right->val + temp);}}return false;}
};

106.从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树

解题思路

一个中序、后序确定一个二叉树
一个前序、中序确定一个二叉树
一个前序、后序无法确定一个二叉树

根据中序、后续确定二叉树
根据后序确定根节点，根据中序确定左右子树节点

class Solution {
private:TreeNode* traversal (vector<int>& inorder, vector<int>& 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;}// 切割中序数组// 左闭右开区间：[0, delimiterIndex)vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);// [delimiterIndex + 1, end)vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );// postorder 舍弃末尾元素postorder.resize(postorder.size() - 1);// 切割后序数组// 依然左闭右开，注意这里使用了左中序数组大小作为切割点// [0, leftInorder.size)vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());// [leftInorder.size(), end)vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = traversal(leftInorder, leftPostorder);root->right = traversal(rightInorder, rightPostorder);return root;}
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;return traversal(inorder, postorder);}
};