打印二叉树的边界 [英] To print the boundary of Binary Tree

问题描述

在一次采访中，我被要求打印二叉树的边界。例如。

I have been asked in an interviews to print the boundary of the Binary Tree. For example.

      1
   /    \
  2      3
 /  \   /  \
4    5 6    7
    /   \     \
   8     9     10

答案将是：1、2、4、8、9、10、7、3

Answer will be : 1, 2, 4, 8, 9, 10, 7, 3

我给出了以下答案。

第一种方法：

我使用了 Bool 变量来求解以上问题。

I have used a Bool variable to solve the above problem.

void printLeftEdges(BinaryTree *p, bool print) {
   if (!p) return;
   if (print || (!p->left && !p->right))
       cout << p->data << " ";
   printLeftEdges(p->left, print);
   printLeftEdges(p->right, false);
}

void printRightEdges(BinaryTree *p, bool print) {
   if (!p) return;
   printRightEdges(p->left, false);
   printRightEdges(p->right, print);
   if (print || (!p->left && !p->right))
   cout << p->data << " ";
}

void printOuterEdges(BinaryTree *root) {
   if (!root) return;
   cout << root->data << " ";
   printLeftEdges(root->left, true);
   printRightEdges(root->right, true);
}

他的响应：您使用了 Bool 变量，因此很多次。您能不使用它解决这个问题吗？

His Response : You have used Bool variable so many times. Can you solve this without using that.

第二种方法：

我只是使用树遍历来解决此问题。

I simply used tree traversal to solve this problem.

1. Print the left boundary in top-down manner.
2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts:
     2.1 Print all leaf nodes of left sub-tree from left to right.
     2.2 Print all leaf nodes of right subtree from left to right.
3. Print the right boundary in bottom-up manner.

他的回答：他也对这种方法不满意。他告诉您穿过树3次。太多了如有其他问题，请给出另一个解决方案。

His Response : He was not happy with this method too. He told that you are traversing the tree 3 times. That is too much. Give another solution if you have any.

第三种方法：
这次我进行了级别定单遍历（ BFS）。

 1: Print starting and ending node of each level
 2: For each other node check if its both the children are <b>NULL</b> then print that node too.

他的回答：他似乎也不满意此方法，因为该方法占用了O的额外内存（n）。

His Response : He was not seems happy with this method too because this method takes extra memory of order O(n).

我的问题是，告诉我一个遍历树一次，不使用任何Bool变量且不使用任何额外内存的方法。

My question is that Tell me a method which traverse tree single times, do not use any Bool variable and do not use any extra memory. Is it possible?

推荐答案

我想这应该可以解决问题：

I guess this should do the trick:

traverse(BinaryTree *root)
{
  if (!root) return;
  cout << p->data << " ";
  if (root->left ) traverseL(root->left ); //special function for outer left
  if (root->right) traverseR(root->right); //special function for outer right
}

traverseL(BinaryTree *p)
{
  cout << p->data << " ";
  if (root->left ) traverseL(root->left ); //still in outer left
  if (root->right) traverseC(root->right); 
}

traverseR(BinaryTree *p)
{
  if (root->left ) traverseC(root->left );
  if (root->right) traverseR(root->right); //still in outer right
  cout << p->data << " ";
}

traverseC(BinaryTree *p)
{
  if (!root->left && !root->right) //bottom reached
    cout << p->data << " ";
  else
  {
    if (root->left ) traverseC(root->left );
    if (root->right) traverseC(root->right);
  }
}

以遍历函数。
消除每个方法开头的空查询（避免在每个末端调用一个函数）。
不需要布尔变量，只需使用三种不同的遍历方法：

Start with the traverse function. Got rid of the null-queries at the beginning of each method (avoids one function call at each end). Does not need bool variables, simply uses three different traversal methods:

• 一个用于左边缘，在遍历之前输出节点


• 一个用于右边，遍历后输出节点


• 一个用于所有其他节点，如果没有同级，则输出该节点。
li>

• one for the left edge, outputting the node before traversal
• one for the right edge, outputting the node after traversal
• one for all other nodes, outputting the node if there are no siblings.

这篇关于打印二叉树的边界的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！