java - 尝试使用两个 if 语句打印树的顶 View

Question

问题陈述

你得到一个指向二叉树根的指针。打印二叉树的顶 View 。 你只需要完成这个功能。

我的代码:

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

所以我只想知道我们是否可以一次只执行一个，即是否有一种方法可以在不更改方法的情况下修复我的代码？

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

Answer 1

您的方法不会奏效，因为当您调用 left 或 right 子树时，您会坚持使用它。这种方法的问题在于您只是受树的哪一侧首先调用的驱动。

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

(查看最后的代码，非常简单)

解决这个问题的方法是保持与根的水平距离，然后为每个不同的水平距离打印第一个节点。

什么是水平距离？

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

特定节点的

水平距离定义为距根水平的数量。如果您看到 no.of 边将变为垂直距离。

为了使根左侧的所有节点更容易从负水平距离和右侧正距离开始。

如何计算水平距离？

如果你向右走加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));
}