刷题笔记day18

找树左下角的值

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

用的层序遍历方法，输出最后一层的第一个节点。

自己写的代码

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> tmp;
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                tmp.push_back(cur->val);
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            result.push_back(tmp);
        }
        int index = result.size() - 1;
        return result[index][0];
    }
};

看了题解精简后：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        int result = 0;
        if (root) que.push(root);
        else return root->val;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; ++i) {
                TreeNode* cur = que.front();
                que.pop();
                if (i == 0) result = cur->val;
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return result;
    }
};

递归法：

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            depth++;
            traversal(root->left, depth);
            depth--; // 回溯
        }
        if (root->right) {
            depth++;
            traversal(root->right, depth);
            depth--; // 回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

看了题解后的收获

每一层没必要再把元素都push进vector中了，只需要存储每一层的第一个节点的值就可以。
递归法直接用前序遍历，找最左侧的最大深度就可以。

路径总和

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

要设置一个外部的flag，或者是传入flag的引用，而不是内部的临时变量，不然内部只要最后一条路径不满足条件，flag就会变。

自己写的代码

迭代法：

class Solution {
public:
    bool flag;
    void getsumroottoleaf(TreeNode* node, vector<int>& vec, int targetsum) {
        vec.push_back(node->val);
        if (!node->left && !node->right) {
            int sum = accumulate(vec.begin(), vec.end(), 0);
            if (sum == targetsum) flag = 1;
        }
        if (node->left) 
        {
            getsumroottoleaf(node->left, vec, targetsum);
            vec.pop_back();
        }
        if (node->right) {
            getsumroottoleaf(node->right, vec, targetsum);
            vec.pop_back();
        }
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        vector<int> vc;
        flag = 0;
        getsumroottoleaf(root, vc, targetSum);
        return flag;
    }
};

思路和输出所有路径一样，就是输入输出不一样。

看了题解用count的版本（省去了每遍历一次push一个数值到vector，完成一条路径后再求和的步骤）：

class Solution {
public:
    bool getsumroottoleaf(TreeNode* node, int count, int &flag) {
        count -= node->val;
        if (!node->left && !node->right) {
            if (count == 0) flag = 1;
        }
        if (node->left) 
        {
            getsumroottoleaf(node->left, count, flag);
        }
        if (node->right) {
            getsumroottoleaf(node->right, count, flag);
        }
        return flag;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        int flag = 0;
        getsumroottoleaf(root, targetSum, flag);
        return flag;
    }
};

看了题解后的收获

可以省去每遍历一次push一个数值到vector，完成一条路径后再求和的步骤。

从中序与后序遍历序列构造二叉树

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

没有思路，去看了视频。

自己写的代码

看了题解后写的代码：

class Solution {
public:
    TreeNode* gettree(vector<int>& inorder, int inbegin, int inend, vector<int>& postorder, int postbegin, int postend) {
        if (postend - postbegin == 0) return NULL;

        int rootval = postorder[postend - 1];
        TreeNode* root = new TreeNode(rootval);

        if (postend - postbegin == 1) return root;

        int midindex;
        for (int i = inbegin; i < inend; ++i) {
            if (inorder[i] == rootval) {
                midindex = i;
                break;
            }
        }
        // 切割中序遍历
        int leftinorderbegin = inbegin;
        int leftinorderend = midindex;
        int rightinorderbegin = midindex + 1;
        int rightinorderend = inend;
        // 切割后序遍历
        int leftpostorderbegin = postbegin;
        int leftpostorderend = postbegin + midindex - inbegin;
        int rightpostorderbegin = postbegin + midindex - inbegin;
        int rightpostorderend = postend - 1;
        // 递归
        root->left = gettree(inorder, leftinorderbegin, leftinorderend, postorder, leftpostorderbegin, leftpostorderend);
        root->right = gettree(inorder, rightinorderbegin, rightinorderend, postorder, rightpostorderbegin, rightpostorderend);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return gettree(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

看了题解后的收获

步骤：

后序数组为空集，返回空指针
后序数组最后一个元素为节点元素
寻找中序数组位置作切割点
切中序数组
切后续数组
递归处理前区间后区间