Диагональный обход двоичного дерева  


Сложный уровень средний
Часто спрашивают в Амазонка Набор фактов Фанатики Фуркиты Oracle PayU Quora
Двоичное дерево дерево Обход дерева

Постановка задачи  

Задача «Диагональный обход двоичного дерева» утверждает, что вам дано двоичное дерево, и теперь вам нужно найти диагональный вид для данного дерева. Когда мы видим дерево в правом верхнем углу. Узлы, которые мы видим, - это диагональный вид двоичного дерева.

Пример  

Диагональный обход двоичного деревашпилька

2 7
3 4
5 6

объяснение

На первой диагонали расположены узлы 2, 7. Тогда на второй диагонали будет 3, 4, аналогично для третьей диагонали 5, 6. Таким образом, результат распечатан таким образом, что элементы с той же диагонали находятся в одной строке.

Подход  

Диагональный обход двоичного деревашпилька

Задача просит нас распечатать узлы, видимые нам в правом верхнем углу. Так как же решить проблему?

Мы выполним обход двоичного дерева в порядке. При этом мы будем отслеживать расстояние по диагонали. Каждый раз, когда мы движемся влево, мы добавляем 1 к диагональному расстоянию, а если мы двигались в правильном направлении, мы не добавляем никакого значения к расстоянию. Таким образом, при этом мы будем отслеживать узлы, посещенные в карта. Мы создадим карту с диагональным расстоянием в качестве ключа и вектором в качестве значения. потому что мы добавим в вектор узлы с диагональным расстоянием. И как бы мы прошли через все дерево. После обхода мы бы сохранили узлы в векторах в соответствии с их диагональным расстоянием.

Смотрите также
Поиск в ширину (BFS) для графика

После всех этих вычислений просто распечатайте элементы на карте, отделяя узлы от каждого из векторов.

Код C ++ для печати диагонального обхода двоичного дерева  

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

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

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

void diagonalView(node* root, int dis, map<int, vector<int>> &m){
    if(root){
        m[dis].push_back(root->data);
        // move in the left direction with dis+1 distance
        diagonalView(root->left, dis+1, m);
        // move in the right direction with dis distance
        diagonalView(root->right, dis, m);
    }
}

int main(){
    node *root = create(2);
    root->left = create(3);
    root->right = create(7);
    root->left->left = create(5);
    root->left->right = create(4);
    root->left->right->left = create(6);

    map<int, vector<int>> m;
    diagonalView(root, 0, m);
    for(auto x: m){
        for(auto nodes: x.second)
            cout<<nodes<<" ";
        cout<<endl;
    }
}
2 7
3 4
5 6

Код Java для печати диагонального обхода двоичного дерева  

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = tmp.right = null;
      return tmp;
  }

  static void diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
      if(root != null){
      	Vector<Integer> v = m.get(dis);
      	if(v == null){
      		v = new Vector<Integer>();
      		v.add(root.data);
      	}
      	else
      		v.add(root.data);
          m.put(dis, v);
          // move in the left direction with dis+1 distance
          diagonalView(root.left, dis+1, m);
          // move in the right direction with dis distance
          diagonalView(root.right, dis, m);
      }
  }

  public static void main(String[] args){
    node root = create(2);
      root.left = create(3);
      root.right = create(7);
      root.left.left = create(5);
      root.left.right = create(4);
      root.left.right.left = create(6);

      Map<Integer, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
      diagonalView(root, 0, m);
      for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
          System.out.println(entry.getValue());
  }
}
[2, 7]
[3, 4]
[5, 6]

Анализ сложности  

Сложность времени

O (NlogN), потому что мы прошли по дереву и обновили значения. Поскольку мы использовали карту, вставка, удаление и поиск выполняются за время O (logN).

Смотрите также
Найдите узел с минимальным значением в дереве двоичного поиска

Космическая сложность

НА), потому что мы храним все узлы на карте. Сложность пространства линейна.