426 binary tree (513. find the value in the lower left corner of the tree, 112. sum of paths, 106. construct a binary tree from the middle order and post order traversal sequence, 654. maximum binary

513. Find the value in the lower left corner of the tree

class Solution {
    
public:
    int findBottomLeftValue(TreeNode* root) {
    
        queue<TreeNode*> que;
        if (root == nullptr) return 0;
        int res = 0;
        que.push(root);

        while (!que.empty())
        {
    
            int size = que.size();

            for (int i = 0; i < size; i++)
            {
    
                TreeNode* node = que.front();
                que.pop();

                if (i == 0)  res = node->val;

                if (node->left)  que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return res;
    }
};

112. The sum of the paths

class Solution {
    
public:
    bool traversal(TreeNode* cur, int count)
    {
    
        if (cur->left == nullptr && cur->right == nullptr && count == 0) return true;
        if (cur->left == nullptr && cur->right == nullptr)   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 targetSum) {
    

        if (root == nullptr) return false;
        return traversal(root, targetSum - root->val);
    }
};

106. Construct binary tree from middle order and post order traversal sequence

654. The largest binary tree

class Solution {
    
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    
        TreeNode* node = new TreeNode(0);

        if (nums.size() == 1)
        {
    
            node->val = nums[0];
            return node;
        }

        int maxValue = 0;
        int maxValueIndex = 0;
        for (int i = 0; i < nums.size(); i++)
        {
    
            if (nums[i] > maxValue)
            {
    
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }

        node->val = maxValue;

        if (maxValueIndex > 0)
        {
    
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            node->left = constructMaximumBinaryTree(newVec);
        }

        if (maxValueIndex < (nums.size() - 1))
        {
    
            vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};