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);}
};

中间四行不注释掉会报错。