2つのifステートメントを使用してツリーの上面図を印刷しようとしています

問題文

二分木のルートへのポインタが与えられます。二分木の上面図を印刷します。機能を完了するだけです。

私のコード：

void top_view(Node root)
 {  
       Node r = root;

       if(r.left!=null){
          top_view(r.left);
          System.out.print(r.data + " ");
        }
       if(r.right!=null){
          System.out.print(r.data + " ");
          top_view(r.right);
        }
}

関数が呼び出されるたびに2つのifステートメントが実行されますが、実行するのに必要なのは1つだけです。switchを試しましたが、定数式エラーが発生します。私はすでにこの問題の別の解決策を見つけました。

したがって、一度に実行する場合に1つしか作成できないかどうか、つまり、アプローチを変更せずにコードを修正する方法はありますか？

問題のリンク： https://www.hackerrank.com/challenges/tree-top-view

この問題は、以下を使用することで非常に簡単に解決できます。

スタック：ルートと左側のサブツリーを印刷します。

キュー：適切なサブツリーを印刷します。

関数は次のようになります。

 void topview(Node root)
 {
     if(root==null)
      return;
     Stack<Integer> s=new Stack<Integer>();
     s.push(root.data);
     Node root2=root;
     while(root.left!=null)
     {
      s.push(root.left.data);
      root=root.left;
     }
     while(s.size()!=0)
      System.out.print(s.pop()+" ");

     Queue<Integer> q=new LinkedList<Integer>(); 
     q.add(root2.right.data);
     root2=root2.right;     
     while(root2.right!=null)
     {
      q.add(root2.right.data);
      root2=root2.right;
     }
     while(q.size()!=0)
      System.out.print(q.poll()+" ");
 }

あなたが電話しleftたりrightサブツリーしたりするとき、あなたはそれに固執するだけなので、あなたのアプローチはうまくいきません。このアプローチの問題は、ツリーのどちら側が最初に呼び出されるかによって駆動されることです。

他の誰かが言ったように、スタックとキューを使用してそれを解決できるかもしれませんが、以下はより単純で直感的なアプローチだと思います：

（最後にコードを参照してください、それは非常に簡単です）

これを解決するためのアプローチはhorizontal distance、ルートから維持し、異なるごとに最初のノードを出力することhorizontal distanceです。

水平距離とは何ですか？

追加した画像を撮っています。

Horizontal distance特定の場合nodeは、水平方向のルートからの数として定義されます。垂直距離になるエッジの数が表示された場合。

ルートの左側にあるすべてのノードの処理を簡単にするために、負の水平距離と右側の正の距離から始めます。

水平距離はどのように計算しますか？

右add 1に行く場合は、左に行く場合はを追加し-1ます。

そう

    horizontal distance of 3 = 0
    
    horizontal distance of 5 = -1
    horizontal distance of 1 = -2
    horizontal distance of 9 = -1
    horizontal distance of 4 = 0

    horizontal distance of 2 =  1
    horizontal distance of 6 =  0
    horizontal distance of 7 =  2
    horizontal distance of 8 =  1

ノードの3,4,6水平距離は同じで0、どういう意味ですか？

つまり、上から見ると、これらのノードはすべて、その1つ上に垂直に並んでいます。

それらが垂直に並んでいる場合、どちらが見えますか？

ルートから最初に到達できるもの。

どちらに最初に到達できるかをどのように見つけますか？

いつものようにBFS

これはあなたの例のソリューションをどのように印刷しますか？

5つの異なる水平距離値{-1、-2,0,1,2}があります

hor dist        Nodes

   0      - {3,6,8} // 3 comes first in BFS so print 3
  -1      - {5,9}   // 5 comes first in BFS so print 5
  -2      - {1}     // just print 1
   1      - {2}     // just print 2
   2      - {7}     // just print 7

したがって、{3,5,1,2,7}が出力されます

HashSet<Integer> set = new HashSet<>();
Queue<QueueItem> queue = new LinkedList<>();
queue.add(new QueueItem(root, 0)); // Horizontal distance of root is 0

while (!queue.isEmpty())
{
    QueueItem temp = queue.poll();
    int hd = temp.hd;
    TreeNode n = temp.node;

    // If this is the first node at its horizontal distance,
    // then this node is in top view
    if (!set.contains(hd))
    {
        set.add(hd);
        System.out.print(n.key + " ");
    }

    if (n.left != null)
        queue.add(new QueueItem(n.left, hd-1));
    if (n.right != null)
        queue.add(new QueueItem(n.right, hd+1));
}
    

左側を再帰で印刷し、右側を単純なwhileループを使用して印刷すると、解決策は非常に簡単です。

 void for_left(node *root)
{
    if(!root->left)
        {
        cout<<root->data<<" ";
        return;
    }
    for_left(root->left);
    cout<<root->data<<" ";
    return;

}

void top_view(node * root)
{
    for_left(root->left);
    cout<<root->data<<" ";
    while(root->right)
        {
        cout<<(root->right)->data<<" ";
        root=root->right;
    }


}

これは実際に機能します。キューは必要ありませんが、親への参照がないため、左側からバックトラックするためにスタックを使用します。

void top_view(Node root)
{
    Stack<Node> p = new Stack<Node>();
    Node current = root;
    while (current != null) 
    {
        p.push(current);
        current = current.left;
    }

    while (p.peek() != root) 
    {
        System.out.print(p.pop().data + " ");
    }

    current = root;
    while (current != null) 
    {
        System.out.print(current.data + " ");
        current = current.right;
    }
}

解決策はここにあります-GitハブのURL

ツリーが以下のように不均衡な状態にある場合、バランスの取れたツリーに関するハッカーランクの質問が何であれ、注意してください。

    1
  /   \
2       3
  \   
    4  
      \
        5
         \
           6

これらの種類のツリーには、ここのgeeksforgeeksで定義されているいくつかの複雑なロジックが必要です-GeeksforGeeks

私のJava実装が添付されています。ツリーの左側は再帰的に解決するとより興味深いものになりますが、文字列を逆にする（以下の私の方法）方が簡単で、1つのメソッドを使用するだけで済みました。

public void top_view(Node root){

    String output = "";

    Node left = root.left;
    Node right = root.right;

    String leftOutput = "";
    while(left != null){
        leftOutput += left.data + " ";
        left = left.left;
    }

    String left = "";
    for(int i = leftOutput.length - 1; i >= 0; i--){
        left += leftOutput.substring(i, i+1);
    }

    output += left;

    output += " " + root.data + " ";

    while(right != null){
        output += right.data + " ";
        right = right.right;
    }

    output = output.substring(1, output.length());
    System.out.println(output);
}

void top_view(Node root)    
{    
    if(root.left!=null) top_view(root.left);   

    if(root.left!=null || root.right!=null)
         System.out.print(root.data + " ");

    if(root.right!=null) top_view(root.right);        
}

C ++でのより単純なアプローチ

`// printing top view of the tree
void left_array(node *p)
{
    if(p==NULL)
    return;
    else
    {
        left_array(p->left);
        cout<<p->data<<" ";
    }
}
void right_array(node *p)
{
    if(p==NULL)
    return;
    else
    {
        cout<<p->data<<" ";
        right_array(p->right);
    }

}
void top_view(node * root)
{   int i=0;
node *t1=root;
node *t2=root;
    left_array(t2);
    right_array(t1->right);

}`

子ノードの長いブランチを処理する非常に単純な再帰ソリューション。これは、水平距離の概念を使用して解決されます。

public void printTopView(BNode root) {
        Map<Integer, Integer> data = new TreeMap<Integer, Integer>();
        printTopViewRecursive(data, root, 0);
        for(int key : data.keySet()) {
            System.out.print(data.get(key) +" ");
        }
    }


    private void printTopViewRecursive(Map<Integer, Integer> hDMap, BNode root, int hD) {
        if(root == null)
            return;
        if(!hDMap.containsKey(hD)) {
            hDMap.put(hD, root.data);
        }
        printTopViewRecursive(hDMap, root.left,hD - 1);
        printTopViewRecursive(hDMap, root.right, hD + 1);
    }

Javarecursivishソリューションで。C ++コードから変換

void top_view(Node root)
{
    left_array(root);
    right_array(root.right);
}

void left_array(Node p)
{
    if(p==null)
        return;
    else
    {
        left_array(p.left);
        System.out.printf("%d ",p.data);
    }
}
void right_array(Node p)
{
    if(p==null)
        return;
    else
    {
        System.out.printf("%d ",p.data);
        right_array(p.right);
    }
}

void top_view(Node root)
 {
    Node left = root;
    Node right = root;
    print_left(root.left);
    System.out.print(root.data + " ");
    print_right(root.right) ;
 }

void print_left(Node start)
 {
    if(start != null)
     {
       print_left(start.left);
       System.out.print(start.data + " "); 
     } 
 }

void print_right(Node start)
 {
    if(start != null)
    {
       System.out.print(start.data + " ");    
       print_right(start.right);
    }     
  } 

それを行うための1つの単純な再帰的方法：

void top_view(Node root)
{
    print_top_view(root.left, "left");
    System.out.print(root.data  + " ");
    print_top_view(root.right, "right");
}

void print_top_view(Node root, String side) {
    if(side.equals("left")) {
        if(root.left != null) {
            print_top_view(root.left, "left"); 
        }
       System.out.print(root.data + " ");
    } else if(side.equals("right")) {
        System.out.print(root.data + " ");
        if(root.right != null) {
          print_top_view(root.right, "right");  
        } 
    }
}

if(root){
if(root->left !=NULL || root->right !=NULL){
    if(root->left)
        top_view(root->left);

     cout<<root->data<<" ";

     if(root->right)
        top_view(root->right);

}}

これは、c ++のバイナリツリーのトップビューのコードです。

void topview（node * root、queue＆Q）

{{

if(!root)
    return;
map<int,int> TV;
Q.push(root);
TV[root->data]=0;
map<int,int>:: iterator it;
int min=INT_MAX,max=INT_MIN;
while(!Q.empty())
{
    node* temp =Q.front();
    Q.pop();
    int l=0;

    for(it=TV.begin();it!=TV.end();it++)
    {
        if(it->first==temp->data)
        {
            l=it->second;
           break;
        }

    }
    if(l<min) 
        {min=l;}
    if(l>max) 
        max=l;
    if(temp->left)
    {
        Q.push(temp->left);
        TV[temp->left->data] = l-1;
    }
    if(temp->right)
    {
        Q.push(temp->right);
        TV[temp->right->data] = l+1;
    }
}
cout<<max<<min<<endl;
for(int  i =min;i<=max;i++)
{
    for(it=TV.begin();it!=TV.end();it++)
    {
        if(it->second==i)
        {
            cout<<it->first;
            break;
        }
    }
}

}

void topview_aux（node * root）

{{

queue<node*> Q;

topview(root,Q);

}

@Karthikが言及したものと非常によく似たアプローチですが、順序を維持しながら、印刷を最後まで延期し、トップビューノードを両端キューで順序付けたままにすることです。

• BFSを使用して注文を保証します
• 各ラウンドでは、現在のノードの水平距離が前のラウンドで到達した最大距離（左側のノードの負の距離）よりも大きいかどうかを確認します。
• 両端キューの左端に-ve距離（左位置）が追加された新しいトップビューノードと、右端に+ ve距離が追加された右ノード。

Javaのサンプルソリューション

import java.util.*;

class Node {
  int data;
  Node left;
  Node right;

  public Node(int data) {
    this.data = data;
  }
}

enum Position {
  ROOT,
  RIGHT,
  LEFT
}

class NodePositionDetails {
  Node node;
  // Node position in the tree
  Position pos;
  // horizontal distance from the root (-ve for left nodes)
  int hd;

  public NodePositionDetails(Node node, Position pos, int hd) {
    this.node = node;
    this.pos = pos;
    this.hd = hd;
  }
}

public class TreeTopView {
  public void topView(Node root) {
    // max horizontal distance reached in the right direction uptill the current round
    int reachedRightHD = 0;
    // max horizontal distance reached in the left direction uptill the current round
    int reachedLeftHD = 0;

    if (root == null)
      return;

    // queue for saving nodes for BFS
    Queue < NodePositionDetails > nodes = new LinkedList < > ();

    // Double ended queue to save the top view nodes in order
    Deque < Integer > topViewElements = new ArrayDeque < Integer > ();

    // adding root node to BFS queue 
    NodePositionDetails rootNode = new NodePositionDetails(root, Position.ROOT, 0);
    nodes.add(rootNode);

    while (!nodes.isEmpty()) {
      NodePositionDetails node = nodes.remove();

      // in the first round, Root node is added, later rounds left and right nodes handled in order depending on BFS. if the current horizontal distance is larger than the last largest horizontal distance (saved in reachedLeftHD and reachedRightHD)
      if (node.pos.equals(Position.LEFT) && node.hd == reachedLeftHD - 1) {
        topViewElements.addFirst(node.node.data);
        reachedLeftHD -= 1;
      } else if (node.pos.equals(Position.RIGHT) && node.hd == reachedRightHD + 1) {
        topViewElements.addLast(node.node.data);
        reachedRightHD += 1;
      } else if (node.pos.equals(Position.ROOT)) { // reachedLeftHD == 0 && reachedRightHD ==0
        topViewElements.addFirst(node.node.data);
      }

      // Normal BFS, adding left and right nodes to the queue
      if (node.node.left != null) {
        nodes.add(new NodePositionDetails(node.node.left, Position.LEFT, node.hd - 1));
      }
      if (node.node.right != null) {
        nodes.add(new NodePositionDetails(node.node.right, Position.RIGHT, node.hd + 1));
      }
    }

    // print top elements view
    for (Integer x: topViewElements) {
      System.out.print(x + " ");
    }
  }
}

そしてテストのために：

  public static void main(String[] args) throws java.lang.Exception {
    /**
       Test Case 1 & 2
        1
       /  \
      2    3
     / \   
    7    4  
   /      \ 
  8        5
            \
             6

       Test Case 3: add long left branch under 3  (branch : left to the 3   3-> 8 -> 9 -> 10 -> 11

       **/

    Node root = new Node(1); //hd = 0
    // test Case 1 -- output: 2 1 3 6
    root.left = new Node(2); // hd = -1
    root.right = new Node(3); // hd = +1
    root.left.right = new Node(4); // hd = 0
    root.left.right.right = new Node(5); // hd = +1
    root.left.right.right.right = new Node(6); // hd = +2

    // test case 2 -- output: 8 7 2 1 3 6 
    root.left.left = new Node(7); // hd = -2
    root.left.left.left = new Node(8); // hd = -3

    // test case 3 -- output: 11 7 2 1 3 6 
    root.left.left.left = null;
    root.right.left = new Node(8); //hd = 0
    root.right.left.left = new Node(9); // hd = -1
    root.right.left.left.left = new Node(10); // hd = -2
    root.right.left.left.left.left = new Node(11); //hd = -3

    new TreeTopView().topView(root);
  }

最も単純な再帰的ソリューション

void top_view(Node root)
{
 // For left side of the tree
    top_view_left(root);
 // For Right side of the tree
    top_view_right(root.right);
}

void top_view_left(Node root){
     if(root != null)
  {     
     // Postorder
     top_view_left(root.left);
     System.out.print(root.data + " ");
  }  
}

void top_view_right(Node root){
    if(root != null)
  {
        //  Preorder
      System.out.print(root.data + " ");
      top_view_right(root.right);
  }  
}

この：

import queue

class NodeWrap:
    def __init__(self, node, hd):
        self.node = node
        #horizontal distance
        self.hd = hd

def topView(root):
    d = {}
    q = queue.Queue()
    q.put(NodeWrap(root, 0))
    while not q.empty():
        node_wrap = q.get()
        node = node_wrap.node
        current_hd = node_wrap.hd
        if d.get(current_hd) is None:
            d[current_hd] = node
            print(node.info, end=" ")
        if node.left is not None:
            q.put(NodeWrap(node.left, current_hd - 1))
        if node.right is not None:
            q.put(NodeWrap(node.right, current_hd + 1))

Pythonでソリューションを機能させる必要がありますが、何らかの理由で、hackerrank.comの7つから6つのテストケースで失敗します。なぜそれが起こっているのか誰かが私に説明できますか？

「左」と「右」の機能を実行するだけの人は、タスクを理解していません。

Pythonソリューション

def topView(root):
    q = deque()
    #Adding root node to the deque along with its Horizontal Distance from root.
    q.append([root,0])
    
    #Dictionary to store the {Horizontal Distance: First Node that has this distance}
    s = {}
    
    #Breadth First Traversal - [To keep track of the first Node that is visited.]
    while q:
        temp = q.popleft()
        #Horizontal Distance from Root
        d = temp[1]
        
        #Adding the Left Child to the Queue (if Exists)
        if temp[0].left is not None:
            q.append([temp[0].left, d-1])
        
        #Adding the Right Child to the Queue (if Exists)
        if temp[0].right is not None:
            q.append([temp[0].right, d+1])
        
        #Adding the Horizontal Distance and the First Node that has this distance to Dictionary.
        if d not in s:
            s[d] = temp[0].info
    
    #Printing out the Top View of Tree based on the values in the Dictionary - From least to Highest Horizontal Distance from Root Node.
    for i in sorted(s):
        print(s[i], end=" ")

def printTopView（root）：

lst=[]
current1=root.left
while current1!=None:
    lst.append(current1.key)
    current1=current1.left
lst.reverse()
current2=root
while current2!=None:
    lst.append(current2.key)
    current2=current2.right

print(*lst)

上記の回答の一部は機能しません。コメントしてみましたが、これまでコメントしたことがないので、どうやら正しいスコアが出ていません。

問題は、ノードの正しい順序を確認するために、ツリーの幅優先探索を実行する必要があることです。「隠された」ノードを除外するために、別のWebサイトが各ノードのランク付けを提案しました。ルートは0です。ノードの左側にあるすべてのブランチの親ランクは-1です。右側のすべてのブランチの親ランクは+1です。祖先のランクが重複しているノードはすべて除外されます。

次に、選択したノードをランク​​順に印刷します。これはすべての場合に機能します。