4

二分木が与えられた場合、同じ垂直線にあるノードの垂直方向の合計を見つけます。すべての合計を異なる垂直線に出力します。

同じ垂直線とは何かを理解するには、まず水平距離を定義する必要があります。2 つのノードの水平距離 (HD) が同じ場合、それらは同じ垂直線上にあります。HD の考え方は単純です。ルートの HD は 0 で、右端 (右のサブツリーに接続する端) は +1 水平距離と見なされ、左端は -1 水平距離と見なされます。たとえば、上のツリーでは、ノード 4 の HD は -2、ノード 2 の HD は -1、ノード 5 と 6 の HD は 0、ノード 7 の HD は +2 です。

例:

    1
  /   \
 2     3
/ \   / \
4  5  6  7

ツリーには 5 つの垂直線があります

Vertical-Line-1 にはノード 4 が 1 つしかありません => 垂直方向の合計は 4 です

Vertical-Line-2: ノード 2 が 1 つしかない => 垂直方向の合計は 2

Vertical-Line-3: 3 つのノードがあります: 1,5,6 => 垂直合計は 1+5+6 = 12

Vertical-Line-4: ノード 3 が 1 つしかない => 垂直方向の合計は 3

Vertical-Line-5: ノード 7 が 1 つしかない => 垂直方向の合計は 7

したがって、期待される出力は 4、2、12、3、および 7 です。

私の解決策： この問題の ao(nlong(n)) 解決策を考えます。アイデアは次のとおりです。

(1) preorder トラバーサルを使用してすべてのノードの HD を取得し、HD とそれに関連付けられたノードを配列に格納します。

(2) 配列を HD で並べ替える

(3) ソートされた配列を走査して結果を出力します。

これは、この問題に最適なものではないと確信しています。より良い解決策を教えてくれる人はいますか?

4

10 に答える 10

11

最初のトラバーサルですべてを行うことはできませんか? HD から sum への辞書 (ハッシュ マップ) を定義します。そして、アクセスするノードごとに、その値を正しい辞書キーに追加します - これがO(n)解決策です。

d = {}

def traverse(node, hd):
  if not node:
    return
  if not hd in d:
    d[hd] = 0
  d[hd] = d[hd] + node.value
  traverse(node.left, hd - 1)
  traverse(node.right, hd + 1)

あとは電話するだけtraverse(root, 0)

于 2013-01-23T17:10:31.427 に答える
0

これは O(n)` で実行される私のソリューションです

 #include <iostream>
 #include <vector>
 using namespace std;

 vector<int> v;
 int size;

typedef struct node
{
int data;
struct node *left, *right ;
} node, *ptr;



ptr newNode(int item)
{
ptr temp =  new node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}

void printVerticalSumUtil(ptr root, int line)
{

if (root == NULL) return;
else
{

    v[line] += root->data;
    printVerticalSumUtil(root->left, line - 1);
    printVerticalSumUtil(root->right, line + 1);
}


}

void printVerticalSum(ptr root)
{
if (root == NULL)
    return;

//Calculating the line No for the root
ptr curr = root;
int line = 0;
while (curr->left != NULL)
{
    curr = curr->left;
    line++;
}
size = 2 * line + 1;  //Total No of Lines
line++;      //Adjusting line no for root

for (int i = 1; i <= size; ++i)   //Initializing lines to zero
    v.push_back(0);

printVerticalSumUtil(root, line);

for (int i = 1; i <= size; ++i)
{
    cout << "Sum of Line " << i << " is " << v[i] << endl;
}
}

int main()
{

ptr root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);

printVerticalSum(root);

return 0;
}`
于 2014-08-24T06:43:19.610 に答える
0

次のコードは仕事をします：

使用言語 : Java

    //  Algorithm for calculating the vertical sum of a binary tree.
static void verticalSum(Node root, int[] sum, int index)
{
    /*
       The sum array contains the sum of each 
       vertical line starting from the leftmost vertical line.
    */
    if(root==null)
    {
        return;
    }
    else
    {
        sum[index]+=(int)root.data;
        verticalSum(root.left, sum, index-1);
        verticalSum(root.right, sum, index+1);
    }
}

次のコードを使用して上記の関数を呼び出す必要があります。

//Algorithm for calculating the vertical sum of a binary tree.
int level=countLevels(root);
int a=1,d=2,n=level;
int sizeOfArray= a+(n-1)*d;
int index=sizeOfArray/2;
int[] sum=new int[sizeOfArray];
verticalSum(root, sum, index);
System.out.print("Vertical Sum of the binary tree is : ");
for(int i=0;i<sizeOfArray;i++)
{
    System.out.print(", " + sum[i]);
}

countLevels(root) 関数を以下に示します。

//  Algorithm for calculating the number of levels
static int countLevels(Node root)
{
    int count=0,c=1,i=0,level=0;
    Queue<Node> queue=new LinkedList<Node>();
    Node temp = null;
    queue.add(root);
    while(true)
    {
        if(queue.isEmpty())
        {
            break;
        }
        level++;
        for(i=0;i<c;i++)
        {
            temp=queue.remove();
            if(temp.left!=null)
            {
                queue.add(temp.left);
                count++;
            }
            if(temp.right!=null)
            {
                queue.add(temp.right);
                count++;
            }
        }
        c=count;
        count=0;
    }
    return level;
}
于 2016-11-24T17:54:37.843 に答える
0

解決が遅くなり申し訳ありません。これを解決するにはいくつかの方法があります。Itay Karo は、hashmap を使用した優れたソリューションを既に提供しています。二重にリンクされたリンク リストを使用することもできます。

  • ルート ノードと空の二重リスト listNode から開始します
  • rootNode の値を現在の listNode に追加します
  • 左に移動するたびに、listNode.left と root.left を渡し、step1 と 2 を再帰的に呼び出します。
  • 右側のノードについても同様に、listNode.right と root.right を渡します。コードは次のとおりです。

printVerticalSum(TreeNode root)
{
   if(root==null)
       return -1;
    allocate node doubleLinkList //initialize,
    printVerticalSumUtil(root, doubleLinkList); 
    //write the function to print double linked list
    System.out.println(doubleLinkList.toString())
}



printVerticalSumUtil(TreeNode root, ListNode listNode)
{
  if(root==NULL) return;



if(root.left!=NULL)
    if(listNode.prev!=NULL)
      listNode.prev.data += root.data;
    else
      ListNode t = new ListNode(root.data);
      t.next=listNode; 
      listNode.prev = t;
    findVerticalSum(root.left, listNode.prev)



if(root.right!=NULL)
    if(listNode.next!=NULL)
      listNode.next.data += root.data;
    else
      ListNode t = new ListNode(root.data);
      t.prev=listNode; 
      listNode.next = t;
    findVerticalSum(root.right, listNode.next)
}
詳細はこちら - http://k2code.blogspot.in/2011/12/vertical-sum-of-binary-tree.html。ありがとう。

于 2016-03-13T06:55:58.013 に答える