513. 找樹左下角的值
題目鏈接：https://leetcode.cn/problems/find-bottom-left-tree-value/
算法思想：
求深度最深的那一層的最左邊的節(jié)點锚烦。那只要找到深度最深的那一層，然后取得遍歷到的第一個節(jié)點就行帝雇。
因此可以采用前序遍歷涮俄。
代碼
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/
算法思想：
前序遍歷（其實沒有前，因為沒有對中節(jié)點做什么處理）
首先需要確定遞歸返回的條件：
遍歷到葉子節(jié)點的時候判斷是否滿足條件尸闸，滿足返回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/
算法思想：
使用回溯法解決：回溯法是在遞歸函數(shù)的下一行寫的。注意回溯法吮廉，要有進(jìn)有出苞尝。
加上了之后，要減回去宦芦。
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.從中序與后序遍歷序列構(gòu)造二叉樹
題目鏈接：
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
算法思想：
根據(jù)后續(xù)遍歷的結(jié)果確定根節(jié)點宙址，根據(jù)根節(jié)點確定，從中序遍歷中確定左右子樹的切割點踪旷，從而確定左右子樹的大小曼氛。再使用左子樹的大小，去后續(xù)遍歷中找到左右子樹的切割點令野，進(jìn)行遞歸舀患。
/**
* 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; //
? ? ? ? //根據(jù)后續(xù)遍歷確定根節(jié)點的值，去中序遍歷的數(shù)組中尋找左右子樹的分割點
? ? ? ? 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. 從前序與中序遍歷序列構(gòu)造二叉樹
題目鏈接：
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
算法思想：
根據(jù)前序遍歷確定根節(jié)點气破，去中序遍歷中尋找中序遍歷的切割點聊浅，從而確定左右子樹的條件。
要明確循環(huán)終止的條件：根節(jié)點為空或者走到葉子節(jié)點時。
/**
* 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;
? ? ? ? }
? ? ? ? //根據(jù)中序遍歷低匙，確定開始和結(jié)束
? ? ? ? int i;
? ? ? ? for(i=in_s;i<in_e;i++) //找到了中序遍歷的切割點
? ? ? ? {
? ? ? ? ? ? if(preorder[pre_s]==inorder[i])
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? //確定前序遍歷的左葉子節(jié)點的結(jié)束為止
? ? ? ? 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;
? ? ? ? // 中序遍歷的開始和結(jié)束
? ? ? ? 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);
? ? }
};
