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

data-structures java tree treeview binary-tree

2022-09-04 20:51:53

问题陈述

您将获得一个指向二叉树根的指针。打印二叉树的顶视图。您只需完成该功能即可。

我的代码：

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 语句，但我只需要其中一个语句即可执行。我尝试切换，但它给出了恒定的表达式错误。我已经为这个问题找到了不同的解决方案。

所以我只想知道如果一次执行，我们是否只能做一个，也就是说，有没有办法在不改变方法的情况下修复我的代码？

enter image description here

问题链接：https://www.hackerrank.com/challenges/tree-top-view

答案 1

你的方法不会起作用，因为当你调用或子树时，你只会坚持下去。这种方法的问题在于，你只是被树的哪一边首先调用。leftright

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

（看最后的代码，很简单）

解决此问题的方法是从 root 进行维护，并为每个不同的 .horizontal distancehorizontal distance

什么是水平距离？

我只是在拍摄您添加的图像。

enter image description here

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 是什么意思？

这意味着当你从顶部看到所有这些节点都在垂直的一条线上时。

如果他们在垂直的线上，你会看到哪一条？

可以首先从根部到达的那个。

您如何找到可以先到达哪一个？

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

答案 2

如果您通过递归打印左侧，并使用简单的 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;
    }


}