Tìm giá trị góc trái dưới cùng của cây

Phương pháp đệ quy:

class Solution {
public:
    void findBottomLeftValueHelper(TreeNode* node, int& maxDepth, int currentDepth, int& result) {
        if (node == nullptr) return;
        if (currentDepth > maxDepth) {
            maxDepth = currentDepth;
            result = node->val;
        }
        findBottomLeftValueHelper(node->left, maxDepth, currentDepth + 1, result);
        findBottomLeftValueHelper(node->right, maxDepth, currentDepth + 1, result);
    }

    int findBottomLeftValue(TreeNode* root) {
        int maxDepth = -1;
        int result = 0;
        findBottomLeftValueHelper(root, maxDepth, 0, result);
        return result;
    }
};

Phương pháp lặp:

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

Tổng đường đi trong cây

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false;
        if (root->left == nullptr && root->right == nullptr && root->val == targetSum) return true;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

Xây dựng cây từ dãy trung và hậu thứ tự

Quá trình xây dựng cây gồm sáu bước:

• Bước 1: Nếu dãy rỗng, trả về null.
• Bước 2: Lấy phần tử cuối cùng của dãy hậu làm gốc.
• Bước 3: Tìm vị trí của phần tử này trong dãy trung.
• Bước 4: Cắt dãy trung thành hai phần: bên trái và bên phải.
• Bước 5: Cắt dãy hậu thành hai phần tương ứng.
• Bước 6: Gọi đệ quy để xây dựng các nhánh trái và phải.

class Solution {
public:
    TreeNode* buildTreeHelper(const std::vector<int>& inorder, const std::vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd) return nullptr;

        int rootVal = postorder[postEnd];
        TreeNode* root = new TreeNode(rootVal);

        int rootIndex = inStart;
        while (inorder[rootIndex] != rootVal) ++rootIndex;

        int leftSize = rootIndex - inStart;
        root->left = buildTreeHelper(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
        root->right = buildTreeHelper(inorder, postorder, rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);

        return root;
    }

    TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
        return buildTreeHelper(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
};