打印二叉树的边界

Question

我在采访中被要求打印二叉树的边界.例如.

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

答案是:1,2,4,8,9,10,7,3

我给出了以下答案.

第一种方法:

我使用Bool变量来解决上述问题.

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变量了.你能不解决这个问题吗？

第二种方法:

我只是使用树遍历来解决这个问题.

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次.那太过分了.如果你有任何解决方案,请提供另

第三种方法: 这次我去了Level Order遍历(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)内存.

我的问题是告诉我一个遍历树的方法,不要使用任何Bool变量,也不要使用任何额外的内存.可能吗？

Answer 1

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

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

从traverse功能开始.在每个方法的开头摆脱了null查询(避免在每一端都有一个函数调用).不需要bool变量,只需使用三种不同的遍历方法:

• 一个用于左边缘,在遍历之前输出节点
• 一个用于右边缘,在遍历后输出节点
• 一个用于所有其他节点,如果没有兄弟节点则输出节点.