Упрощение функции сравнения двух бинарных деревьев

Условие

Представлена реализация функции isSameTree, в которой применяются вложенные условные операторы. Необходимо сделать код более лаконичным и понятным, убрав лишние вложения, но при этом сохранить корректную рекурсивную проверку идентичности двух бинарных деревьев.

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

bool isSameTree(TreeNode* node1, TreeNode* node2) {
    if (!node1 && !node2)
        return true;
    if (node1 && node2) {
        if (node1->val == node2->val) {
            if (isSameTree(node1->left, node2->left)) {
                return isSameTree(node1->right, node2->right);
            }
        }
    }
    return false;
}

Ответ

Уберите вложенные if через раннюю проверку пустых указателей и объединение остальных условий оператором &&. Короткое замыкание сохранит порядок и безопасность проверки.

Эквивалентный вариант:

bool isSameTree(TreeNode* a, TreeNode* b) {
    if (!a || !b) return a == b;
    return a->val == b->val
        && isSameTree(a->left, b->left)
        && isSameTree(a->right, b->right);
}

Сначала обрабатываются оба случая пустоты, поэтому далее разыменование безопасно. При несовпадении значения или левого поддерева правая ветвь уже не вычисляется. Сложность не меняется: O(n) времени в худшем случае и O(h) стека.