福田蒙派克4s店电话和地址_制作灯笼图片_学生个人网页设计作品_二十四个关键词

• 找到深度最大的点，遍历方式左边节点在右边节点前面，找到就返回，一定就是最左下角的值了

class Solution {
public:int max_depth = -1;int result = 0;int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}void traversal(TreeNode* node, int depth) {if (node->left == nullptr && node->right == nullptr) {if (depth > max_depth) {max_depth = depth;result = node->val;return;}}if (node->left) {depth++;traversal(node->left, depth);depth--;}if (node->right) {depth++;traversal(node->right, depth);depth--;}}
};

• 不需要求路径，需要返回一个bool值代表找没找到

class Solution {
public:int sum = 0;bool hasPathSum(TreeNode* root, int targetSum) {if (root == nullptr) {return false;}sum += root->val;if (root->left == nullptr && root->right == nullptr) {if (sum == targetSum) {return true;}return false;}if (root->left) {bool left = hasPathSum(root->left, targetSum);if(left){return true;}sum -= root->left->val;}if (root->right) {bool right = hasPathSum(root->right, targetSum);if(right){return true;}sum -= root->right->val;}return false;}
};

• 需要求路径，就不用返回值

class Solution {
public:vector<vector<int>> result;vector<int> path;int sum = 0;vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if (root == nullptr) {return result;}sum += root->val;path.push_back(root->val);get_path(root, targetSum);return result;}void get_path(TreeNode* node, int targetSum) {if (node->left == nullptr && node->right == nullptr) {if (sum == targetSum) {result.push_back(path);}return;}if (node->left) {sum += node->left->val;path.push_back(node->left->val);get_path(node->left, targetSum);sum -= node->left->val;path.pop_back();}if (node->right) {sum += node->right->val;path.push_back(node->right->val);get_path(node->right, targetSum);sum -= node->right->val;path.pop_back();}return;}
};

• 重点是找到前序遍历的第一个节点，在中序遍历中把他一分为二，再把前序遍历剩下的节点也一分为二，不断重复这个过程

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (preorder.size() == 0) {return nullptr;}int val = preorder[0];int index = 0;for (int i = 0; i < inorder.size(); i++) {if (inorder[i] == val) {index = i;}}vector<int> left_preorder;vector<int> right_preorder;vector<int> left_inorder;vector<int> right_inorder;for (int i = 0; i < index; i++) {left_inorder.push_back(inorder[i]);}for (int i = index + 1; i < inorder.size(); i++) {right_inorder.push_back(inorder[i]);}for (int i = 1; i <= index; i++) {left_preorder.push_back(preorder[i]);}for (int i = index + 1; i < preorder.size(); i++) {right_preorder.push_back(preorder[i]);}TreeNode* node = new TreeNode(val);node->left = buildTree(left_preorder, left_inorder);node->right = buildTree(right_preorder, right_inorder);return node;}
};

• 重点是从后序遍历中找到最后一个节点，在中序遍历中把他一分为二，再把后序遍历的剩下的节点也一分为二，不断重复这个过程

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (postorder.size() == 0) {return nullptr;}int val = postorder[postorder.size() - 1];int index = 0;for (int i = 0; i < inorder.size(); i++) {if (inorder[i] == val) {index = i;}}TreeNode* node = new TreeNode(val);vector<int> left_inorder;vector<int> right_inorder;vector<int> left_postorder;vector<int> right_postorder;for (int i = 0; i < index; i++) {left_inorder.push_back(inorder[i]);}for (int i = index + 1; i < inorder.size(); i++) {right_inorder.push_back(inorder[i]);}for (int i = 0; i < index; i++) {left_postorder.push_back(postorder[i]);}for (int i = index; i < postorder.size() - 1; i++) {right_postorder.push_back(postorder[i]);}node->left = buildTree(left_inorder, left_postorder);node->right = buildTree(right_inorder, right_postorder);return node;}
};