513. 找树左下角的值
题目链接：https://leetcode.cn/problems/find-bottom-left-tree-value/
算法思想：
求深度最深的那一层的最左边的节点。那只要找到深度最深的那一层，然后取得遍历到的第一个节点就行。
因此可以采用前序遍历。
代码
class Solution {
public:
int final = INT_MIN;
int final_deep = INT_MIN;
void findbottom(TreeNode* node, int height)
{
if (node==NULL)
return;
if(node->left==NULL && node->right == NULL)
{
if(final_deep < height)
{
final = node->val;
final_deep = height;
}
}
findbottom(node->left, height+1);
findbottom(node->right, height+1);
}
int findBottomLeftValue(TreeNode* root) {
//使用前序遍历
int height = 0;
findbottom(root, height);
return final;
}
};
112. 路径总和
题目链接：
https://leetcode.cn/problems/path-sum/
算法思想：
前序遍历（其实没有前，因为没有对中节点做什么处理）
首先需要确定递归返回的条件：
遍历到叶子节点的时候判断是否满足条件，满足返回true，否则返回false
代码：
class Solution {
public:
bool haspath(TreeNode* root, int target, int sum)
{
if(root==NULL)
return false;
if(root->left==NULL&&root->right==NULL && sum+root->val == target)
return true;
bool left = haspath(root->left, target, sum+root->val);
if(left)
return true;
bool right = haspath(root->right, target, sum+root->val);
if(right)
return true;
return false;
}
bool hasPathSum(TreeNode* root, int targetSum) {
return haspath(root, targetSum, 0);
}
};
113. 路径总和 II
题目链接：
https://leetcode.cn/problems/path-sum-ii/
算法思想：
使用回溯法解决：回溯法是在递归函数的下一行写的。注意回溯法，要有进有出。
加上了之后，要减回去。
class Solution {
public:
void path(TreeNode* root, int targetSum, vector<vector<int>>& res, vector<int>& cur)
{
if(root==NULL)
return ;
cout<<"target:"<<targetSum<<endl;
if(root->left==NULL&&root->right==NULL&&targetSum==root->val)
{
cur.push_back(root->val);
res.push_back(cur);
cur.pop_back();
return;
}
if(root->left==NULL&&root->right==NULL&&targetSum==root->val)
{
return;
}
if(root->left)
{
cur.push_back(root->val);
targetSum = targetSum-root->val;
// cout<<"left-sum:"<<targetSum<<endl;
path(root->left, targetSum, res, cur);
targetSum = targetSum + root->val;
cur.pop_back();
}
if(root->right)
{
cur.push_back(root->val);
targetSum = targetSum-root->val;
// cout<<"right-sum:"<<targetSum<<endl;
path(root->right, targetSum, res, cur);
targetSum = targetSum + root->val;
cur.pop_back();
}
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int> > result;
vector<int> cur;
path(root, targetSum, result, cur);
return result;
}
};
106.从中序与后序遍历序列构造二叉树
题目链接：
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
算法思想：
根据后续遍历的结果确定根节点，根据根节点确定，从中序遍历中确定左右子树的切割点，从而确定左右子树的大小。再使用左子树的大小，去后续遍历中找到左右子树的切割点，进行递归。
/**
* 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* buildtree(vector<int>& inorder, int in_start, int in_end, vector<int>& postorder, int post_start, int post_end)
{
// cout<<"in_start:"<<in_start<<" in_end:"<<in_end<<" post_start"<<post_start<<" post_end"<<post_end<<endl;
if(post_end<post_start)
{
// cout<<"in if: post_start"<<post_start<<" post_end"<<post_end<<endl;
return NULL;
}
int now = postorder[post_end];
// cout<<"now:"<<now<<endl;
TreeNode* node = new TreeNode(now);
if(in_end==in_start)
return node;
int i=in_start; //
//根据后续遍历确定根节点的值，去中序遍历的数组中寻找左右子树的分割点
for(i=in_start;i<=in_end;i++)
{
// cout<<"while i:"<<i<<endl;
if(now == inorder[i]) //找到了中序遍历的分割点
{
break;
}
}
// cout<<"i:"<<i<<endl;
int left_size = i-in_start;
node->left = buildtree(inorder, in_start,i-1,postorder,post_start,post_start+left_size-1);
node->right = buildtree(inorder,i+1,in_end, postorder, post_start+left_size,post_end-1);
// cout<<"node->val:"<<node->val<<endl;
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildtree(inorder,0,inorder.size()-1, postorder,0,postorder.size()-1);
}
};
105. 从前序与中序遍历序列构造二叉树
题目链接：
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
算法思想：
根据前序遍历确定根节点，去中序遍历中寻找中序遍历的切割点，从而确定左右子树的条件。
要明确循环终止的条件：根节点为空或者走到叶子节点时。
/**
* 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* buildtree(vector<int>& preorder, int pre_s, int pre_e, vector<int>& inorder, int in_s, int in_e)
{
if(pre_e<pre_s)
return NULL;
TreeNode* node = new TreeNode(preorder[pre_s]);
if(pre_e==pre_s)
{
return node;
}
//根据中序遍历，确定开始和结束
int i;
for(i=in_s;i<in_e;i++) //找到了中序遍历的切割点
{
if(preorder[pre_s]==inorder[i])
break;
}
//确定前序遍历的左叶子节点的结束为止
int preorder_left_start = pre_s+1;
int preorder_left_end = pre_s+(i-in_s);
int preorder_right_start = pre_s+(i-in_s)+1;
int preorder_right_end = pre_e;
// 中序遍历的开始和结束
int inorder_left_start = in_s;
int inorder_left_end = i-1;
int inorder_right_start = i+1;
int inorder_right_end = in_e;
node->left = buildtree(preorder, preorder_left_start,preorder_left_end, inorder,inorder_left_start,inorder_left_end);
node->right = buildtree(preorder,preorder_right_start,preorder_right_end, inorder,inorder_right_start,inorder_right_end);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildtree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
}
};
