二叉树中同一层的叶子

Question

给定一棵二叉树，检查所有叶子是否在同一层。

输入：

输出：0

说明：第 10、15 和 30 个叶子不在同一层。
方法：每个节点的左子树和右子树的高度应该相同。

我的代码：

int height(Node* root){
    if(root == NULL) return 0;
    return 1 + max(height(root->left), height(root->right));
}
bool check(Node *root)
{
    if(root == NULL) return true;
    if(root->left == NULL && root->right == NULL) return true;
    if(root->left == NULL || root->right == NULL) return false;
    int l = height(root->left);
    int r = height(root->right);
    if(l == r) return true;
    return false;
    
}

问题： 但是此代码不适用于多个测试用例。谁能帮我弄清楚为什么？

测试用例失败：
2910 7670 牛 712 4700 牛 8459 2271 牛 332 8570 牛 7403 8390 牛 9496 8400 牛 8771 6683 牛 1647 440 牛 1979 1254

它的正确输出是： 1个

我的代码输出是： 0

字符串表示：

Answer 1

您只是在检查根左侧最深的叶子是否与根右侧最深的叶子高度相同。您需要检查最小高度和最大高度。

std::pair<int, int> heights(Node * node) {
    if (node->left && node->right) {
        auto [lmin, lmax] = heights(node->left);
        auto [rmin, rmax] = heights(node->right);
        return { 1 + std::min(lmin, rmin), 1 + std::max(rmax, lmax) };
    } else if (node->left) {
        auto [min, max] = heights(node->left);
        return { 1 + min, 1 + max };
    } else if (node->right) {
        auto [min, max] = heights(node->right);
        return { 1 + min, 1 + max };
    } else {
        return { 0, 0 };
    }
}

bool check(Node * node) {
    auto [min, max] = heights(node);
    return min == max;
}

二叉树中同一层的叶子

Leaf at same level in binary tree

c++

binary-tree

data-structures