算法随想Day16【二叉树】| LC513-找树左下角的值、LC112-路径总和、LC106-从中序与后序遍历序列构造二叉树

LC513. 找树左下角的值

这道题用层次遍历，更容易做

int findBottomLeftValue(TreeNode* root)
{
    int result = 0;
    int size = 0;
    queue<TreeNode*> que;
    TreeNode* curr = nullptr;
    if (root != nullptr)
    {
        que.push(root);
    }
    while (que.empty() != true)
    {
        size = que.size();
        result = que.front()->val;
        for (int i = 0; i < size; i++)
        {  
            curr = que.front();
            que.pop();
            if (curr->left != nullptr)
            {
                que.push(curr->left);
            }
            if (curr->right != nullptr)
            {
                que.push(curr->right);
            }
        }
    }
    return result;
}

记录下错误：

开始没定义size，直接写为for (int i = 0; i < que.size(); i++)，这是一段错误的代码，因为for内对queue进行的push和pop操作都会影响其size()值，这里很容易忽略出错

LC112. 路径总和

递归做法一次通过，递归回溯时，再拼接当前节点在前面

class Solution
{
public:
    int flag;
    void checkPathSum(TreeNode* root, int sum, int& targetSum)
    {
        if (root != nullptr) return;  //力扣非要加多这一句才给通过，不理解
        sum += root->val;
        if (root->left == nullptr && root->right == nullptr)
        {
            //sum += root->val;
            if (targetSum == sum)
            {
                flag = true;
            }
            return ;
        }
        checkPathSum(root->left, sum, targetSum);
        checkPathSum(root->right, sum, targetSum);
    }
    bool hasPathSum(TreeNode* root, int targetSum)
    {
        int sum = 0;
        flag = false;
        if (root == nullptr)
        {
            return false;
        }
        checkPathSum(root, sum, targetSum);
        return flag;
    }
};

总结思考：

• 回溯，左右子树不相干的递归（LC112. 路径总和、LC257. 二叉树的所有路径）：用前序，先处理中，终止条件为if (root->left == nullptr && root->right == nullptr)，后面左右子树分别递归，两者平行不相干。
• 左右子树不相干的递归（LC404. 左叶子之和，LC110. 平衡二叉树）：回溯时，当前节点的总值会跟左右两子树都相关，可能是相加之和sum = leftsum + rightsum + (root->left == nullptr && root->right == nullptr && is_left == 1 ? root->val : 0)，也可能是两者比较if (abs(leftheight - rightheight) > 1)。

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

递归的函数，传参传的是值，而不是地址，所以内存消耗比较大。其实可以传引用，然后用指针（索引下标）标明每层对两个数组的操作范围的话，应该可以省下些内存。

class Solution
{
public:
    TreeNode* buildTreeLoop(vector<int> inorder, vector<int> postorder)
    {
        int count = 0;
        int curr_val = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(curr_val);
        ////开始写了这个判断，作为递归终止条件，后面添加下面两个if判断，遂可以省去这个
        // if (postorder.size() == 1)
        // {
        //     return root;
        // }
        auto it = find(inorder.begin(), inorder.end(), curr_val);
        for (auto i = inorder.begin(); i != it; i++)
        {
            ++count;
        }
        ////这两个if判断不能丢，否则可能导致指针访问越界
        if (it != inorder.begin())  //当it指向inorder.begin()时，说明当前节点已经没有左子树
            root->left = buildTreeLoop(vector<int>(inorder.begin(), it), vector<int>(postorder.begin(), postorder.begin() + count));
        if (it != inorder.end() - 1)  //当it指向inorder.end() - 1时，说明当前节点已经没有右子树
            root->right = buildTreeLoop(vector<int>(it + 1, inorder.end()), vector<int>(postorder.begin() + count, postorder.end() - 1));
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        return buildTreeLoop(inorder, postorder);
    }
};