LeetCode 513 找树左下角的值
这题要求找树最底层最左边节点的值,用单纯的迭代法、递归法都不太好处理,一般的层序遍历法也不太行。但是可以修改下层序遍历,改成每一层从右往左遍历,依次往下,这样子访问的最后一个节点就是最底层最左边的节点了。这也用到了广度优先搜索的方法。
代码如下:
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> myque;
TreeNode* cur = root;
myque.push(root);
while (!myque.empty()) {
int num = myque.size();
while (num--) {
cur = myque.front();
myque.pop();
if (cur->right) myque.push(cur->right);
if (cur->left) myque.push(cur->left);
}
}
return cur->val;
}
};
深度优先搜索是递归的改版。之后有时间再写下。
LeetCode 112 路径总和
和昨天一样的回溯法
class Solution {
private:
int num = 0;
int sum = 0;
public:
void backtracking(TreeNode* cur, int targetSum) {
if (!cur->left && !cur->right) {
if (sum == targetSum) num++;
return;
}
if (cur->left) {
sum += cur->left->val;
backtracking(cur->left, targetSum);
sum -= cur->left->val;
}
if (cur->right) {
sum += cur->right->val;
backtracking(cur->right, targetSum);
sum -= cur->right->val;
}
}
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
targetSum -= root->val;
backtracking(root, targetSum);
return (bool)num;
}
};
也可以像求高度一样用递归。这里就不写了。
LeetCode 106 从中序与后序遍历构造二叉树
这题感觉确实是有难度了。首先是对于中序遍历和后序遍历确定一棵树的理解,其次是递归时递归逻辑的选择和确定。还可以用map降低时间复杂度,以及要注意先递归构建右子树,再递归构建左子树,这样方便从后往前地从后序遍历中取数作为根节点查找依据。之所以这样也是因为迭代法求后序遍历时所收获的一些感悟和心得——后续遍历是中右左遍历方式的反转,每次放入的节点一定先是局部状态下的根节点,后是局部状态下的右节点,再是局部状态下的左节点。
代码如下:
class Solution {
public:
TreeNode* mybuildTree(vector<int>& inorder, int in_l, int in_r,
vector<int>& postorder, int post_l, int post_r) {
if (in_l > in_r) return nullptr;
// if (in_l == in_r) {
// TreeNode* newNode = new TreeNode(inorder[in_l]);
// return newNode;
// }
int rootval = postorder[post_r];
int in_rootIndex = 0;
for (int i = in_l; i <= in_r; i++) {
if (inorder[i] == rootval) {
in_rootIndex = i;
break;
}
}
TreeNode* root = new TreeNode(rootval);
if (in_rootIndex > in_l) {
root->left = mybuildTree(inorder, in_l, in_rootIndex -1, postorder, post_l, post_l + (in_rootIndex - 1-in_l));
}
if (in_r > in_rootIndex) {
int first_r = inorder[in_rootIndex + 1];
int post_rstart = 0;
for (int i = post_l; i <= post_r; i++) {
if (postorder[i] == first_r) {
post_rstart = i;
break;
}
}
root->right = mybuildTree(inorder, in_rootIndex + 1, in_r, postorder, post_rstart, post_r - 1);
}
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return mybuildTree(inorder, 0, inorder.size() - 1, postorder, 0, inorder.size() - 1);
}
};
中间四行不注释掉会报错。