编写计算给定树的树叶数的函数

Question

树是由节点组成的抽象数据结构。每个节点只有一个父节点和零个或多个子节点。 每棵树都有一个称为根的特殊节点，它没有父节点。如果一个节点没有子节点，则该节点称为叶节点。
树可以用数组P表示，其中P [i]作为节点i的父节点。对于根节点r，P [r]等于-1。

编写一个函数来计算给定树的叶数。

例如，由数组{1,3,1，-1,3}表示的树有5个节点，0到4个，其中3个节点是树叶（0,2和4，因为所有其他节点都在至少一个子节点）。

using System; 

public class TreeArray { 
    public static int CountLeaves(params int[] tree) { 
     throw new NotImplementedException("Waiting to be implemented"); 
    } 
    public static void main(string[] args) { 
     Console.WriteLine(TreeArray.CountLeaves(1,3,1,-1,3)); 
    } 
} 

解决方案，我试图：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 
using System.Diagnostics; 
using System.Collections; 

namespace Test 
{ 
    class CreateTreeFromParentArray 
    { 
    public static int INVALID_INDEX = -1; 
    public class TreeNode 
    { 
     internal object data; 
     public TreeNode left; 
     public TreeNode right; 
     public TreeNode(object data) 
     { 
      this.data = data; 
     } 
    } 
    public TreeNode root; 
    //Main Method 
    static void Main(string[] args) 
    { 
     CreateTreeFromParentArray solution = new 
     CreateTreeFromParentArray(); 

     int[] tree = { 1, 3, 1, -1, 3 }; 
     int LeaveCount = solution.CountLeaves(tree); //Count Leaf Leaves 

     Console.WriteLine("Leaf Node Count:" + LeaveCount); 
     Console.ReadKey(); 
    } 

    //Method for Counting Leaf Nodes 
    public int CountLeaves(params int[] tree) 
    { 
     CreateTreeFromParentArray solution = new 
    CreateTreeFromParentArray(); 
     TreeNode root = solution.constructTreeBottomUp(tree); //Created Tree 
     with given Array 

     if (root == null) { return 0; } 

     Stack<TreeNode> stack = new Stack<TreeNode>(); 
     TreeNode node = new TreeNode(root); 
     int count = 0; 

     while (!(root == null)) 
     { 
      if (root.left != null) stack.Push(root.left); 
      if (root.right != null) stack.Push(root.right); 

      if (root.left == null && root.right == null) 
      { 
       count++; 
      } 
      if (stack.Count == 0) 
      { 
       break; 
      } 
      else 
      { 
       root = stack.Pop(); 
      } 
     } 
     return count; 
    } 
    public TreeNode constructTreeTopDown(int[] parent) 
    { 
     int rootIndex = INVALID_INDEX; 
     for (int i = 0; i < parent.Length; i++) 
     { 
      if (parent[i] == -1) 
      { 
       rootIndex = i; 
       break; 
      } 
     } 
     if (rootIndex != INVALID_INDEX) 
     { 
      this.root = new TreeNode(rootIndex); 
     } 
     constructTreeTopDownRec(root, rootIndex, parent); 

     return root; 
    } 
    public TreeNode constructTreeBottomUp(int[] parent) 
    { 
     TreeNode[] constructed = new TreeNode[parent.Length]; 

     for (int i = 0; i < constructed.Length; i++) 
     { 
      constructNode(i, constructed, parent); 
     } 
     return root; 
    } 
    public void constructNode(int i, TreeNode[] constructed, int[] parent) 
    { 
     if (constructed[i] != null) 
     { 
      return; 
     } 
     if (parent[i] == -1) 
     { 
      constructed[i] = new TreeNode(i); 
      root = constructed[i]; 
      return; 
     } 

     if (constructed[parent[i]] == null) 
     { 
      constructNode(parent[i], constructed, parent); 
     } 

     constructed[i] = new TreeNode(i); 

     if (constructed[parent[i]] != null) 
     { 
      if (constructed[parent[i]].left == null) 
      { 
       constructed[parent[i]].left = constructed[i]; 
      } 
      else 
      { 
       constructed[parent[i]].right = constructed[i]; 
      } 
     } 
    } 
    public void constructTreeTopDownRec(TreeNode currentNode, int currentNodeValue, int[] parent) 
    { 
     int indexFirstChild = -1, indexSecondChild = -1; 
     for (int i = 0; i < parent.Length; i++) 
     { 
      if (currentNodeValue == parent[i]) 
      { 
       if (indexFirstChild == -1) 
       { 
        indexFirstChild = i; 
       } 
       else 
       { 
        indexSecondChild = i; 
        break; 
       } 
      } 
     } 

     if (indexFirstChild == -1) 
     { 
      return; 
     } 

     currentNode.left = new TreeNode(indexFirstChild); 
     constructTreeTopDownRec(currentNode.left, indexFirstChild, parent); 

     if (indexSecondChild != -1) 
     { 
      currentNode.right = new TreeNode(indexSecondChild); 
      constructTreeTopDownRec(currentNode.right, indexSecondChild, parent); 
     } 
    } 
} 
} 

，但这是不正确的

Answer 1

只是跟踪哪些指标是不是叶子，你会看到在树索引第一次算吧不是一片叶子。那么叶子的数量就是树中节点的数量减去非叶子的数量。

bool[] seen = new bool[tree.Length]; 
int notLeaves = 0; 
for(int i=0; i < tree.Length; i++){ 
    if(tree[i] == -1) { 
     continue; 
    } 
    if(!seen[tree[i]]){ 
     seen[tree[i]] = true; 
     notLeaves++; 
    } 
} 

return tree.Length - notLeaves; 

或者使用LINQ

int leaves = tree.Length - tree.Where(n => n != -1).Distinct().Count();