day16 二叉树4
513.找树左下角的值
迭代法：
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
deque<TreeNode*> q;
q.push_back(root);
int res;
while (!q.empty()) {
int n = q.size();
res = q.front()->val;
while (n --) {
TreeNode *node = q.front();
q.pop_front();
if (node->left) {
q.push_back(node->left);
}
if (node->right) {
q.push_back(node->right);
}
}
}
return res;
}
};
递归法：
class Solution {
public:
int maxDepth = INT_MIN;
int result;
void traversal(TreeNode* node, int height) {
if (node->left == nullptr && node->right == nullptr) {
if (height > maxDepth) {
maxDepth = height;
result = node->val;
}
if (node->left) {
traversal(node->left, height + 1);
}
if (node->right) {
traversal(node->right, height + 1);
}
}
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return result;
}
};
112. 路径总和
class Solution {
public:
bool result = false;
void traversal(int targetSum, TreeNode *cur) {
if (cur == nullptr) {
return;
}
if (cur->val == targetSum && cur->left == nullptr && cur->right == nullptr) {
result = true;
return;
}
traversal(targetSum - cur->val, cur->left);
traversal(targetSum - cur->val, cur->right);
}
bool hasPathSum(TreeNode* root, int targetSum) {
traversal(targetSum, root);
return result;
}
};
113. 路径总和ii
class Solution {
public:
vector<vector<int>> res;
void traversal(vector<int> &path, TreeNode *cur, int targetSum) {
if (cur == nullptr) {
return;
}
if (cur->left == nullptr && cur->right == nullptr && targetSum == 0) {
res.push_back(path);
return;
}
if (cur->left) {
path.push_back(cur->left->val);
traversal(path, cur->left, targetSum - cur->left->val);
path.pop_back();
}
if (cur->right) {
path.push_back(cur->right->val);
traversal(path, cur->right, targetSum - cur->right->val);
path.pop_back();
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return res;
}
vector<int> path;
path.push_back(root->val);
traversal(path, root, targetSum - root->val);
return res;
}
};
106.从中序与后序遍历序列构造二叉树
很有思路，但是写不对。。。。
class Solution {
public:
int findIndex(int val, vector<int> &inorder) {
for (int i = 0; i < inorder.size(); i ++) {
if (inorder[i] == val) {
return i;
}
}
return -1;
}
TreeNode* traversal(vector<int> &inorder, vector<int> &postorder) {
if (postorder.size() == 0) {
return nullptr;
}
TreeNode* node = new TreeNode(postorder[postorder.size() - 1]);
int index = findIndex(node->val, inorder);
vector<int> leftInorder(inorder.begin(), inorder.begin() + index);
vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());
vector<int> leftPostorder(postorder.begin(), postorder.begin() + index);
vector<int> rightPostorder(postorder.begin() + index, postorder.end() - 1);
node->left = traversal(leftInorder, leftPostorder);
node->right = traversal(rightInorder, rightPostorder);
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return traversal(inorder, postorder);
}
};
以上写法，每次递归都定义了新的vector，既耗时又耗空间，优化版：
class Solution {
public:
int getIndex(int val, vector<int> &inorder) {
for (int index = 0; index < inorder.size(); index ++) {
if (inorder[index] == val) {
return index;
}
}
return -1;
}
TreeNode* traversal(vector<int> &inorder, vector<int> &postorder, int inBegin, int inEnd, int postBegin, int postEnd) {
if (inBegin >= inEnd || postBegin >= postEnd) {
return nullptr;
}
TreeNode *node = new TreeNode(postorder[postEnd - 1]);
int index = getIndex(postorder[postEnd - 1], inorder);
int leftInBegin = inBegin;
int leftInEnd = index;
int leftPostBegin = postBegin;
int leftPostEnd = postBegin + (index - inBegin);
int rightInBegin = index + 1;
int rightInEnd = inEnd;
int rightPostBegin = postBegin + (index - inBegin);
int rightPostEnd = postEnd - 1;
node->left = traversal(inorder, postorder, leftInBegin, leftInEnd, leftPostBegin, leftPostEnd);
node->right = traversal(inorder, postorder, rightInBegin, rightInEnd, rightPostBegin, rightPostEnd);
return node;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = postorder.size();
return traversal(inorder, postorder, 0, n, 0, n);
}
};
105.从前序与中序遍历序列构造二叉树
class Solution {
public:
int getIndex(vector<int> &inorder, int val) {
for (int index = 0; index < inorder.size(); index ++) {
if (inorder[index] == val) {
return index;
}
}
return -1;
}
TreeNode* traversal(vector<int> &preorder, vector<int> &inorder) {
if (preorder.size() == 0) {
return nullptr;
}
TreeNode *node = new TreeNode(preorder[0]);
int index = getIndex(inorder, preorder[0]);
vector<int> leftPre(preorder.begin() + 1, preorder.begin() + index + 1);
vector<int> rightPre(preorder.begin() + index + 1, preorder.end());
vector<int> leftIn(inorder.begin(), inorder.begin() + index);
vector<int> rightIn(inorder.begin() + 1 + index, inorder.end());
node->left = traversal(leftPre, leftIn);
node->right = traversal(rightPre, rightIn);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return traversal(preorder, inorder);
}
};
优化版：
class Solution {
public:
int getIndex(vector<int> &inorder, int val) {
for (int index = 0; index < inorder.size(); index ++) {
if (inorder[index] == val) {
return index;
}
}
return -1;
}
TreeNode* traversal(vector<int> &preorder, vector<int> &inorder, int leftPre, int rightPre, int leftIn, int rightIn) {
if (leftPre >= rightPre) {
return nullptr;
}
TreeNode *node = new TreeNode(preorder[leftPre]);
int index = getIndex(inorder, preorder[leftPre]);
node->left = traversal(preorder, inorder, leftPre + 1, leftPre + 1 + (index - leftIn), leftIn, leftIn + (index - leftIn));
node->right = traversal(preorder, inorder, leftPre + 1 + (index - leftIn), rightPre, index + 1, rightIn);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
return traversal(preorder, inorder, 0, n, 0, n);
}
};
关键是：确定好右边是不是闭区间，然后就一直按这个写，然后长度length搞清楚。
