设计一个算法（给出伪代码）给定一个二叉树计算 num

Question

设计一个算法（给出伪代码），给定一棵二叉树，计算具有两个children的节点数。你算法的运行时间是多少

我重试了我的问题，有人知道我提供的内容是否正确吗？这是我到目前为止所做的。这是正确的吗？

Function find2Children(T)
Input: a binary search, Tree
Output: number of nodes w / two children

count = 0
inOrderWalk(T)
if((leaf[x] ! = NULL)) && (right[x] ! = NULL))
  count ++
return count

我们只需要搜索 n 个节点的树，所以 O(n) 是我的 TC。

Answer 1

您可以使用递归和深度优先搜索来完成：

Function find2Children(T, startNode)
Input: a binary tree, the node to start searching
Output: number of nodes w / two children

if (startNode == NULL) {
    return 0
}

(left, right) = (left[startNode], right[startNode])

count  = (left != NULL) && (right != NULL) ? 1 : 0
count += find2Children(tree, left) + find2Children(tree, right)

return count

或者没有递归的广度优先搜索：

Function find2Children(T)
nodesToCheck = {rootNode}
i = 0
count = 0

while i < nodesToCheck.length {
    x = nodesToCheck[i]
    (left, right) = (left[x], right[x])
    count += (left != NULL) && (right != NULL) ? 1 : 0
    if (left  != NULL) nodesToCheck.add(left)
    if (right != NULL) nodesToCheck.add(right)

    i++
}

两者都是O(n)。

Answer 2

r这是一个 O(n) 算法。您可以使用任何树遍历算法（按顺序、post-顺序或预顺序）进行计算。下面是先序遍历

find2Children(node)
  if  node == NULL or node.isLeaf()
    return 0

 if node.left != NULL and node.right !=NULL
   return 1+find2Children(node.left)+find2Children(node.right)
 else
  return find2Children(node.left)+find2Children(node.right)

设计一个算法（给出伪代码）给定一个二叉树计算 num

Design an algorithm (give pseudo code) that given a binary tree computes the num

algorithm

computer-science

binary-tree

nodes