給定二叉樹中的垂直和


難度級別
經常問 亞馬遜 Microsoft微軟
二叉樹

問題陳述

“給定二叉樹中的垂直總和”問題指出您得到了一棵二叉樹,我們需要找到每個垂直水平的總和。 垂直水平,是指如果我們在左右方向上以1個單位的距離繪製垂直線,則與第ith條線相交的節點被稱為在第ii個垂直距離處。

輸入

給定二叉樹中的垂直和

3, 5, 2, 5

說明: 值為3的節點處於級別-1,節點1和4處於級別0。因此,它們的總和為5。類似地,我們求解級別1和2的節點。因此答案為3、5、3、5。

給定二叉樹中的垂直和

此處,線下方的數字表示每條線的水平高度。

給定二叉樹中垂直求和的方法

為了解決這個問題,我們將為每個節點分配一些水平級別,並使用 地圖 存儲每個水平級別的答案。 因此,最後,我們獲得了每個級別的總和,因為最後,我們遍歷了該層次的所有節點。 二叉樹.

關於水平距離的方法很簡單。 我們將0分配給根,如果我們移到根的右邊,則將1和-1分配給左邊。 類似地,對於處於水平級別或水平距離“ h”的節點,我們將h-1分配給左側,將h + 1分配給右側。 現在,我們將簡單地遍歷樹,並繼續將每個節點的值添加到地圖上,其中關鍵點是水平距離。

推薦碼

給定二叉樹中垂直和的C ++代碼

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
};

node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
}


void fillVerticalSums(node *root,int horizontalLevel,map<int,int> &verticalSums){

    // base case
    if(!root)
        return;
    // recursively call for the left subtree
    fillVerticalSums(root->left, horizontalLevel-1, verticalSums);
    // add the value of current node to the current horizontal distance
    verticalSums[horizontalLevel] += root->data;
    // recursively call for right subtree
    fillVerticalSums(root->right, horizontalLevel+1, verticalSums);
}

void verticalSum(node *root)
{
    // map which stores the sum of nodes at each horizontal level
    map<int, int> verticalSums;
    fillVerticalSums(root, 0, verticalSums);
    // map stores the data in sorted order
    for(auto x: verticalSums)
        cout<<x.second<<" ";
}

int main()
{
    // here we have made a binary tree
    node *root = create(1);
    root->left = create(3);
    root->right = create(2);
    root->right->left = create(4);
    root->right->right = create(5);
    cout<<"The Vertical Sums: ";
    verticalSum(root);

    return 0;
}
The Vertical Sums: 3 5 2 5

給定二叉樹中垂直和的Java代碼

import java.util.*;
// Class that denotes a node of the tree
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int data) 
    { 
        this.data = data;
        left = right = null; 
    } 
}

class Tree 
{ 
    static Node root;
  static void fillVerticalSums(Node root, int horizontalLevel, TreeMap<Integer, Integer> verticalSums){
  
      // base case
      if(root == null)
          return;
      // recursively call for the left subtree
      fillVerticalSums(root.left, horizontalLevel-1, verticalSums);
      // add the value of current node to the current horizontal distance
      if(verticalSums.containsKey(horizontalLevel))
      	verticalSums.put(horizontalLevel, verticalSums.get(horizontalLevel) + root.data);
      else
      	verticalSums.put(horizontalLevel, root.data);
      // recursively call for right subtree
      fillVerticalSums(root.right, horizontalLevel+1, verticalSums);
  }

  static void verticalSum(Node root)
  {
      // map which stores the sum of nodes at each horizontal level
      TreeMap<Integer, Integer> verticalSums = new TreeMap<Integer, Integer>();
      fillVerticalSums(root, 0, verticalSums);
      // map stores the data in sorted order
      for(Map.Entry<Integer, Integer> entry: verticalSums.entrySet())
      	System.out.print(entry.getValue()+" ");
  }
  
    public static void main(String args[]) 
    { 
    	// here we have made a binary tree
        Tree tree = new Tree(); 
        tree.root = new Node(1); 
        tree.root.left = new Node(3); 
        tree.root.right = new Node(2); 
        tree.root.right.left = new Node(4); 
        tree.root.right.right = new Node(5); 
  
        System.out.print("The Vertical Sums: ");
        verticalSum(tree.root);
    }
}
The Vertical Sums: 3 5 2 5

複雜度分析

時間複雜度

O(N對數N)  因為我們僅遍歷了僅遍歷N個節點的樹。 而且自從插入,搜索和刪除以來,每項操作耗時N次。 這就是為什麼我們有一個log N因子的原因。

空間複雜度

上) 因為我們在樹中只存儲了N個節點。