与えられたツリーの葉の数を数える関数を書く

Question

ツリーは、ノードからなる抽象的なデータ構造です。各ノードには親ノードと子ノードが1つしかありません。 各ツリーには、親ノードを持たないルートと呼ばれる1つの特別なノードがあります。子ノードがない場合、ノードはリーフと呼ばれます。
ツリーは、ノードPの親としてP [i]の配列Pで表すことができます。ルートノードrの場合、P [r]は-1に等しくなります。

特定のツリーの葉数を数える関数を作成します。

たとえば、配列{1,3,1、-1,3}で表されるツリーには5つのノード、0から4のノードがあり、そのうち3つのノードはリーフ（0,2および4）です。少なくとも1つの子ノード）。私が試した

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();