switch - java while




嘗試使用兩個if語句來打印樹的頂視圖 (10)

問題陳述

給你一個指向二叉樹根的指針。 打印二叉樹的頂視圖。 你只需要完成這個功能。

我的代碼:

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);
        }
}

這兩個if語句每次調用函數都會執行,但是我只需要其中的一個來執行。 我試過開關,但它給不斷的表達錯誤。 我已經找到了這個問題的一個不同的解決方案。

所以我只想知道,如果我們一次只能執行一個,那麼有沒有辦法在不改變方法的情況下修復我的代碼呢?

問題鏈接: https //www.hackerrank.com/challenges/tree-top-view


你的方法不會工作,因為當你打電話leftright子樹,你會堅持下去。 這種方法的問題是你只是首先調用樹的哪一邊。

也許你可以通過使用棧和隊列來解決這個問題,但是我覺得以下是一個更簡單和更直觀的方法:

(最後看代碼,非常簡單)

解決這個問題的方法是保持與根的horizontal distance ,並為每個不同的horizontal distance打印第一個節點。

什麼是水平距離?

我只是採取您添加的圖像。

特定node Horizontal distance定義為水平根節點的數量。 如果您看不到將成為垂直距離的邊緣。

為了讓所有的根節點左側的節點更容易開始-ve水平距離和右側正距離。

你如何計算水平距離?

如果你正確的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 =  0

節點3,4,6,8有相同的水平距離0是什麼意思?

這意味著當你從上面看到所有的這些節點都在一條垂直線上。

如果他們在垂直線上,你看到了哪一個?

可以從根到達的那個。

你如何找到第一個可以到達的地方?

像往常一樣BFS

這是如何打印解決方案的例子?

有五個不同的水平距離值{-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)    
{    
    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);

}`

這個問題可以很容易地通過使用:

堆棧 :打印根和左子樹。

隊列 :打印正確的子樹。

你的功能應該是這樣的:

 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()+" ");
 }

這一個實際上工作。 不需要隊列,而是使用堆棧來從左側回溯,因為我們沒有引用父進程。

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;
    }
}

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);
    }     
  } 

一個簡單的遞歸方式來做到這一點:

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");  
        } 
    }
}

這是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);

}


最簡單的遞歸解決方案

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);
  }  
}




binary-tree