编写一个布尔函数，给定一棵二叉树，如果树的节点数为偶数，则 returns 为真

Question

问：写一个布尔函数，给定一个二叉树，returns当且仅当树有偶数个节点。一棵空树被认为具有偶数个节点。

备注：

函数应该只有一个参数，一个指向根的指针。

不能使用全局变量。

不能定义附加函数。你可能数不过来的节点数

Answer 1

下面假设单节点组成的树是奇数。也就是说，如果您的树仅包含根节点，则该树的节点数为奇数。不清楚 "empty tree" 在您的描述中的含义。我假设它的意思是，"null root."

一个节点可以被认为是，即使它的 children 有奇数个节点。是的，奇怪。因为你必须计算节点本身。考虑简单的二叉树：

  1
2   3

合起来，节点的children节点数为偶数。但是你也得算根节点。

所以一个 child 必须有偶数个节点，另一个必须有奇数个节点。

考虑一棵更大的树：

       1
   2       3
 4   5       6
7

节点4是偶数。节点 5 是奇数。节点 2 是偶数。节点 6 是奇数。节点 3 是偶数。节点 1 是奇数，因为 children 都是偶数。

真相table，假设偶数=真，奇数=假：

left   right   result
false  false   false
false  true    true
true   false   true
true   true    false

所以如果两者都为真或都为假，则为假。如果其中一个为真，则结果为真。那是 exclusive-or.

这应该递归工作。让我们试试上面的树。

7没有节点，所以结果是奇数。
4 有一个奇数左节点和一个偶数右节点（空节点被认为是偶数）。 4 是偶数。
5没有节点，所以很奇数。
2 是偶数，因为 4 是偶数，5 是奇数。
6是奇数，因为它没有children.
3 是偶数，因为左边是偶数，右边是奇数。
1 是奇数，因为它的左右节点（2 和 3）都是偶数。

根据该描述，您应该能够编写递归函数。

Answer 2

Bool isEven(treepr *p)
{
    if(p)
    {
        if(isEven(p->left) == isEven(p->right))
            return false;
        else
            return true;
    }

    return true;
}

编写一个布尔函数，给定一棵二叉树，如果树的节点数为偶数，则 returns 为真

Write a Boolean function that is given a binary tree and returns true if the tree has an even number of nodes

tree

binary-tree

pointers

nodes

data-structures