找到最大值二叉树的叶节点

Question

       50
     /    \ 
   25      75
  /  \     / \
 15  27   62  79  

depth = 3
total nodes = 7
max leaf nodes = 4

       50
     /    \ 
   25      75
  /  \     / \
 15  27   62  79  
 _    _   _    _ 
 1    1   1    1  = 4

在树满的情况下，这将找到叶节点的总数，但如果树不满并且只知道树的深度，我怎么知道最大值。该树中的叶节点？

// if the tree is full
function total_leafs_nodes(node, level, mxlevel)
  {
      if (node == null) {
        return 1;
      }
      if (node.left == null && node.right == null)
          return 1;

      else if (level == mxlevel)
      {
          return 1;
      }
      return (total_leafs_nodes(node.left, level + 1, mxlevel)
      + total_leafs_nodes(node.right, level + 1, mxlevel));
  }

Answer 1

如果每个节点可以拥有的最大子节点数，那么您可以应用以下内容：

令d等于深度，m为每个节点的最大子节点数，n为可能的节点数，则...

n = m ^ (d - 1)

找到最大值二叉树的叶节点

find max. leaf nodes of a binary tree

javascript

binary-tree