LeetCode513. 找树左下角的值
题目链接：513. 找树左下角的值
初次尝试
后序递归法，传递一个容器保存当前节点的高度和当前节点为根的树左下角的值，递归单层逻辑是如果左子树节点高度不小于右子树，则返回左子树的容器，反之返回右子树的容器。
class Solution {
public:
vector<int> findValue(TreeNode* node) {
if (node == NULL) return {0, 0};
if (node -> left == NULL && node -> right == NULL) return {1, node -> val};
vector<int> left_vec = findValue(node -> left);
vector<int> right_vec = findValue(node -> right);
if (left_vec[0] >= right_vec[0]) return {left_vec[0] + 1, left_vec[1]};
else return {right_vec[0] + 1, right_vec[1]};
}
int findBottomLeftValue(TreeNode* root) {
return findValue(root)[1];
}
};
看完代码随想录后的想法
前序递归回溯法也可以解，当然使用层序迭代法是最简单最合适的，题解代码如下。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
int result = 0;
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;
}
};
LeetCode112. 路径总和
题目链接：112. 路径总和
初次尝试
使用的是带回溯的递归法，遇到叶子节点后判断路径和是否与目标值相等，代码写的比较完整且直观，有不少简化空间。
class Solution {
public:
bool pathSum(TreeNode* node, int sum, int targetSum) {
if (node -> left == NULL && node -> right == NULL) {
if ((sum += node -> val) == targetSum) {
return true;
}
}
bool left_bool = false;
bool right_bool = false;
if (node -> left) {
sum += node -> val;
left_bool = pathSum(node -> left, sum, targetSum);
sum -= node -> val;
}
if (node -> right) {
sum += node -> val;
right_bool = pathSum(node -> right, sum, targetSum);
sum -= node -> val;
}
return left_bool || right_bool;
}
bool hasPathSum(TreeNode* root, int targetSum) {
int sum = 0;
if (root) return pathSum(root, sum, targetSum);
else return false;
}
};
看完代码随想录后的想法
如下所示，上述代码还有很多地方可以优化。
不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
class Solution {
private:
bool traversal(TreeNode* cur, int count) {
if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
if (cur->left) { // 左
count -= cur->left->val; // 递归，处理节点;
if (traversal(cur->left, count)) return true;
count += cur->left->val; // 回溯，撤销处理结果
}
if (cur->right) { // 右
count -= cur->right->val; // 递归，处理节点;
if (traversal(cur->right, count)) return true;
count += cur->right->val; // 回溯，撤销处理结果
}
return false;
}
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) return false;
return traversal(root, sum - root->val);
}
};
LeetCode113. 路径总和II
题目链接：113. 路径总和II
初次尝试
递归带回溯法，吸取了上一题题解的思路，一遍ac。
class Solution {
public:
void sumPath(TreeNode* node, int count, vector<int> temp, vector<vector<int>>& ans) {
if (!node -> left && !node -> right && count == 0) ans.push_back(temp);
if (node -> left) {
count -= node -> left -> val;
temp.push_back(node -> left -> val);
sumPath(node -> left, count, temp, ans);
temp.pop_back();
count += node -> left -> val;
}
if (node -> right) {
count -= node -> right -> val;
temp.push_back(node -> right -> val);
sumPath(node -> right, count, temp, ans);
temp.pop_back();
count += node -> right -> val;
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (root) {
int count = targetSum;
vector<int> temp;
vector<vector<int>> ans;
temp.push_back(root -> val);
sumPath(root, count - root -> val, temp, ans);
return ans;
}
else return {};
}
};
看完代码随想录后的想法
思路差不多。
LeetCode106. 从中序与后序遍历序列构造二叉树
题目链接：106. 从中序与后序遍历序列构造二叉树
初次尝试
没有想到什么好的思路。
看完代码随想录后的想法
题解思路大概是：
- 后序数组的最后一个元素值为根节点的值
- 通过根节点分割中序数组，得到左子树和右子树的中序数组
- 通过左子树中序数组的大小，分割后序数组，得到左子树和右子树的后序数组
- 递归，得到左子树和右子树，返回根节点。
class Solution {
public:
TreeNode* traversal(vector<int> inorder, vector<int> postorder) {
if (postorder.size() == 0) return NULL;
int root_value = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(root_value);
if (postorder.size() == 1) return root;
int delimiter_index;
for (delimiter_index = 0; delimiter_index < inorder.size(); delimiter_index++) {
if (inorder[delimiter_index] == root_value) break;
}
vector<int> left_inorder(inorder.begin(), inorder.begin() + delimiter_index);
vector<int> right_inorder(inorder.begin() + delimiter_index + 1, inorder.end());
vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size());
vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end() - 1);
root -> left = traversal(left_inorder, left_postorder);
root -> right = traversal(right_inorder, right_postorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return traversal(inorder, postorder);
}
};