尝试使用两个if语句打印树的顶视图

Question

问题陈述

您将获得指向二叉树根的指针.打印二叉树的顶视图.您只需要完成该功能.

我的代码:

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

Answer 1

你的方法不会起作用,因为当你打电话left或right子树时,你会坚持下去.这种方法的问题在于您只是首先调用树的哪一侧.

也许你可以通过使用堆栈和队列来解决它,就像其他人说的那样,但我觉得以下是一种更简单,更直观的方法:

(最后看到代码,非常简单)

解决这个问题的方法是horizontal distance从root 维护,然后打印每个不同的第一个节点horizontal distance.

什么是水平距离？

我只是拍摄你添加的图像.

Horizontal distance对于特定node的定义为从根水平的数量.如果您看到任何边缘将成为垂直距离.

为了使根在左侧的所有节点更容易,以-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什么意思？

这意味着当你从顶部看到所有这些节点在它上面的垂直线上时.

如果它们垂直排成一行你看到了哪一个？

可以从root首先到达的那个.

你怎么找到第一个可以到达的？

像往常一样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));
}

Answer 2

这个问题可以很容易地通过使用来解决：

Stack：打印根和左子树。

队列：打印右子树。

你的函数应该是这样的：

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