4

给定一棵二叉树，求同一垂直线上的节点的垂直总和。通过不同的垂直线打印所有总和。

要了解什么是相同的垂直线，我们需要先定义水平距离。如果两个节点具有相同的水平距离 (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 => 垂直总和为 4

Vertical-Line-2：只有一个节点 2=> 垂直总和为 2

Vertical-Line-3：具有三个节点：1,5,6 => 垂直总和为 1+5+6 = 12

Vertical-Line-4：只有一个节点 3 => 垂直总和为 3

Vertical-Line-5：只有一个节点 7 => 垂直总和为 7

所以预期的输出是 4、2、12、3 和 7

我的解决方案： 我想出了针对这个问题的 ao(nlong(n)) 解决方案。这个想法是：

(1) 使用前序遍历得到每个节点的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 
#define HD_OFFSET 16

void vertical_sum(Node *node, int hd, int sum[], int *min, int *max){

/* We are offseting the index to access array correctly.
Root will be at HD_OFFSET/2 index and all vertical lines on left will
be at 0 to HD_OFFSET/2 and right side will be on HD_OFFSET/2 to HD_OFFSET */

int index = hd + HD_OFFSET/2;

if(!node) return;

/* to keep track of min and max index filled in sum array */
if(index > (*max)) (*max) = index;
if(index < (*min)) (*min) = index;

sum[index]+= node->value;
/*If we are moving on the left side, 
we will pass index as one less the current */
vertical_sum(node->left, hd-1, sum, min, max);

/*If we are moving on the right side, 
we will pass index as one more the current */
vertical_sum(node->right, hd+1, sum, min, max);
}
于 2015-03-25T11:11:08.547 回答
0

使用级别顺序遍历，使用包含元素的队列以及它们的 HD 值。以下算法将在 O(n) [未运行测试] 中给出解决方案

void findVertSum( struct node *root)
{
 enqueue(root);
 enqueue(0);
 while(!isEmptyQueue())
 {
   tempnode = dequeue();
   vertIndex = dequeue();

   sum[vertIndex] += tempnode->val;  
       // Array cant be used because there will be sum[-1], sum[-2] etc, which will give error. This line hense only gives the idea to store solution.

   if(t->left)
   {
     enqueue(t->left);
     enqueue(vertIndex - 1);
   }

   if(t->right)
   {
     enqueue(t->right);
     enqueue(vertIndex + 1);
   }
}
于 2014-07-10T17:53:44.513 回答
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

这是 C 中的一个。返回时的 vsum 数组将有结果。

void vsum(struct tree *t, int vsum[], int depth)     {

    if (t == NULL)
        return;

    vsum[depth] += t->val;
    depth++;

    vsum(t->left, vsum, depth);
    vsum(t->right, vsum, depth);

}
于 2013-04-23T18:14:17.687 回答
0

这是我在 C# 中的解决方案：请注意顺序很重要，因此我必须创建一个类并应用自定义排序。

public class Location 
{
    public int x, y, val;

    public Location(int x, int y, int val)
    {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

private List<Location> locations;
public IList<IList<int>> VerticalTraversal(TreeNode root)
{
    // Each location is a node's x position, y position, and value
    locations = new List<Location>();
    dfs(root, 0, 0);
    locations.Sort(Comparer<Location>.Create((a,b) =>
    {
        if (a.x != b.x)
            return a.x.CompareTo(b.x);
        return a.y != b.y ? a.y.CompareTo(b.y) : a.val.CompareTo(b.val);
    }));

    var result = new List<IList<int>>();
    result.Add(new List<int>());

    int prev = locations[0].x;

    foreach(Location loc in locations)
    {
        // If the x value changed, it's part of a new report.
        if (loc.x != prev)
        {
            prev = loc.x;
            result.Add(new List<int>());
        }

        // We always add the node's value to the latest report.
        result[result.Count - 1].Add(loc.val);
    }
    return result;
}

private void dfs(TreeNode node, int x, int y)
{
    if (node != null)
    {
        locations.Add(new Location(x, y, node.val));
        dfs(node.left, x - 1, y + 1);
        dfs(node.right, x + 1, y + 1);
    }
}
于 2019-03-07T14:46:57.647 回答
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

这是我在 C++ 中的简单解决方案：- 这里我使用地图根据与中心的水平距离来存储总和。

Node *vsumprint(Node *root,int level,map<int,int> &mp){
    if(root==NULL)return NULL;
    Node *temp = vsumprint(root->left,--level,mp);
    if(temp==NULL){
        level++;
    }
    if(mp.find(level)!=mp.end()){
        mp[level] = root->data+mp[level];
    }
    else{
         mp[level] = root->data+mp[level];
    }
    return vsumprint(root->right,++level,mp);
 }
void printVertical(Node *root)
{
    map<int,int> mp;
    vsumprint(root,0,mp);
    for(auto it:mp){
        cout<<it.second<<" ";
    }

}
于 2017-12-24T14:02:45.540 回答
0

//测试和工作示例

package tree;

    import java.util.TreeMap;

    public class VerticalSumProblem 
    {

        public static void main(String[] args) 
        {
            VerticalSumProblem verticalSum = new VerticalSumProblem();
            TreeNode treeNode = verticalSum.new TreeNode(1);

            treeNode.left = verticalSum.new TreeNode(2);
            treeNode.right = verticalSum.new TreeNode(3);

            treeNode.left.left = verticalSum.new TreeNode(4);
            treeNode.left.right = verticalSum.new TreeNode(5);

            treeNode.right.left = verticalSum.new TreeNode(6);
            treeNode.right.right = verticalSum.new TreeNode(7);

            //treeNode.right.right.left =verticalSum.new TreeNode(8);

            verticalSum.printTree(treeNode);
            verticalSum.findVerticalSum(treeNode);
        }

        private void findVerticalSum(TreeNode root)
        {
            if(root == null) return;

            TreeMap<Integer,Integer> _mappings = new TreeMap<Integer,Integer>();
            findVerticalSum(root,_mappings,0);

            if (_mappings != null) 
            {
                System.out.println(_mappings.entrySet());
            }
        }

        //if goes left --  and if goes right ++
        private void findVerticalSum(TreeNode treeNode,TreeMap<Integer,Integer> mappings, int level)
        {
            if(treeNode == null) return;

            TreeNode treeNodeLeft,treeNodeRight;

            if(treeNode.left != null)
            {
                treeNodeLeft =  treeNode.left;
                findVerticalSum(treeNodeLeft, mappings,level - 1);
            }

            int sum = mappings.get(level) == null ? 0 : mappings.get(level); 
            mappings.put(level, treeNode.data + sum);

            if( treeNode.right != null)
            {
                treeNodeRight =  treeNode.right;
                findVerticalSum(treeNodeRight,mappings, level + 1);
            }
        }



    /* Create following Binary Tree
         1
       /   \
      2      3
     / \    / \
    4   5, 6    7

    */

        private void printTree(TreeNode treeNode)
        {
            TreeNode treeNodeLeft,treeNodeRight;

            if(treeNode == null) return;

            if(treeNode.left != null || treeNode.right != null)
            {
                treeNodeLeft =  treeNode.left;
                treeNodeRight =  treeNode.right;

                System.out.println("rootValue ="+treeNode.data);

                System.out.println("Left child of ="+treeNode.data +" is : "+ getNodedata(treeNodeLeft));   
                System.out.println("Right child of ="+treeNode.data+" is : "+ getNodedata(treeNodeRight)+"\n");

                printTree(treeNodeLeft);
                printTree(treeNodeRight);
            }
        }

        private int getNodedata(TreeNode treeNode)
        {
            if(treeNode != null)
            {
               return treeNode.data;    
            }
            return -1;
        }

        private class TreeNode
        {
            private int data;
            private TreeNode left,right;

            TreeNode(int data)
            {
                this.data = data;
                left = null;
                right = null;
            }
        }

    }



    //vertical sum
    ///   |   |    |   |    | 
    //    |   |    1   |    | 
    ///   |   2    |   3    | 
    //    4   |   5,6  |    7


    //             0 
    //         1        -1
    //     2      0,0        -2
    //
于 2017-08-20T16:29:02.760 回答
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 回答