打印二叉树的边界

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次。那太多了。如果你有其他解决方案，请给出。

第三种方法： 这次我采用了层序遍历（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)空间。

我的问题是：告诉我一种只遍历树一次、不使用任何布尔变量和额外内存的方法。这是否可能？

- Muktinath Vishwakarma

---

我认为O(1)时间的遍历并不是很糟糕！【第二种解决方案】 - Emadpres

@Emadpres 这不是O(1)，而是O(n)。因为我们至少需要遍历所有节点一次。 - Muktinath Vishwakarma

O(1) 指的是 3。遍历 3 次或 1 次并不重要，除非需要使用。 - Emadpres

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变量，只需使用三种不同的遍历方法：

• 一个用于左边缘，输出遍历前的节点
• 一个用于右边缘，输出遍历后的节点
• 一个用于所有其他节点，如果没有兄弟节点则输出该节点。

- azt

---

不用客气。如果您满意，请接受并点赞答案。 - azt

我没有足够的积分来点赞一个解决方案。只要我获得足够的积分，我就会点赞。 - Muktinath Vishwakarma

谢谢。祝你面试顺利。 - azt

你有没有在traverseL中错过节点在左边界但不是叶节点的情况。比如说，当根节点的左子节点为空而右子节点不为空时，这个右子节点有更多的节点在左子节点上。这些节点将不会被打印出来。 - userab

@userab 这有点取决于边界的定义。你说得对，我只考虑了左侧、右侧和叶节点。你所说的更像是每个层级的起始和结束，就像上面提到的第三种方法。对于左侧边缘，可以通过返回迄今为止返回值的最深深度，并在我们比那更深时继续在traverseL路径中进行。对于右侧边缘，向相反方向遍历，对于两者都需要额外的内存。因此，我怀疑问题是否朝着那个方向发展。但是没有具体说明，你可能是正确的。 - azt

谢谢澄清。 - userab

Answer 2

以下是Python3中的递归解决方案，时间复杂度为O(n)。该算法的目的是从上到下打印最左边的节点，从左到右打印叶节点，从下到上打印最右边的节点。为了简化代码并驱动时间复杂度为O(n)，需要添加布尔标志(isLeft,isRight)来进行左右树遍历。

#Print tree boundary nodes
def TreeBoundry(node,isLeft,isRight):
    #Left most node and leaf nodes
    if(isLeft or isLeaf(node)): print(node.data,end=' ')
    #Process next left node
    if(node.getLeft() is not None): TreeBoundry(node.getLeft(), True,False)
    #Process next right node
    if(node.getRight() is not None):TreeBoundry(node.getRight(), False,True)
    #Right most node
    if(isRight and not isLeft and  not isLeaf(node)):print(node.data,end=' ')

#Check is a node is leaf
def isLeaf(node):
   if (node.getLeft() is None and  node.getRight() is None):
       return True
   else:
       return False

#Get started
#https://github.com/harishvc/challenges/blob/master/binary-tree-edge-nodes.py
TreeBoundry(root,True,True)

- harishvc

---

我不确定你的解决方案是否正确。TreeBoundary中的最后一行不仅打印右边界，还打印了从直接右转到达的树中任何节点。相反，您需要跟踪它是否纯粹是通过右转到达的。此外，我不认为布尔值是必要的，因为函数指针可以轻松跟踪三种状态，并且可以避免很多条件检查。 - azt

Answer 3

方法 O(n) 不需要额外空间，单遍历树。

我将树节点分为四种类型的节点

类型1 -> 形成左边界的节点（例如8）

类型0 -> 不形成边界的节点（例如12）

类型3 -> 形成右边界的节点（例如22）

叶子节点（例如4,10,14）

在我的方法中，我只是对树进行递归遍历（稍作修改），其中我的函数具有以下形式

  void recFunc(btNode *temp,int type)
   {
      //Leaf Nodes
     if((temp->left == NULL)&&(temp->right == NULL))
                 cout << temp->data <<  " ";
     // type -1 Nodes must be printed before their children
   else if(type == 1)cout << temp->data << " ";
   else {;}


   if(type == 3)
   {
    if(temp->left)recFunc(temp->left,0);
    if(temp->right)recFunc(temp->right,3);
     //type 3 nodes must be printed after their children
    cout << temp->data << " ";
   }   
   else if(type == 1)
   {
    if(temp->left)recFunc(temp->left,1);
    if(temp->right)recFunc(temp->right,0);
   }
   else if(type == 0)
   {
    if(temp->left)recFunc(temp->left,0);
    if(temp->right)recFunc(temp->right,0);
   }
   else {;}
    }

我修改了哪里

1. 在我的递归函数中，类型为1的节点必须将其左侧节点设置为类型1，并在调用它们的子节点（如果存在）之前打印。
2. 类型为3的节点必须按相反的顺序打印。因此，在调用它们的子节点后才能打印它们。它们还必须将其右侧子节点分配为类型3节点。
3. 类型为0的节点不能打印，并将其子节点分配为类型0节点。
4. 叶节点必须直接打印并返回。

代码链接

- Vinayak Sangar

---

在你给出的树中：如果没有4，则必须打印12。你的代码如何处理这个问题？ - Vivek MVK

Answer 4

//4个不同的列表，分别对应解决方案的4个不同部分 1）左边界 2）右边界 3）左树中的叶子节点 4）右树中的叶子节点

public class PRintBinaryTreeBoundary {


    ArrayList<TreeNode> leftBorderList=new ArrayList<>();
    ArrayList<TreeNode> leftLEafNode=new ArrayList<>();

    ArrayList<TreeNode> rightBorderList=new ArrayList<>();
    ArrayList<TreeNode> rightLEafNode=new ArrayList<>();



    public static void main(String[] args) {
        // TODO Auto-generated method stub
         /*  1
           /    \
          2      3
         /  \   /  \
        4    5 6    7
            /   \     \
           8     9     10*/
        TreeNode one=new TreeNode(1);

        TreeNode two=new TreeNode(2);
        TreeNode three=new TreeNode(3);
        TreeNode four=new TreeNode(4);
        TreeNode five=new TreeNode(5);
        TreeNode six=new TreeNode(6);
        TreeNode seven=new TreeNode(7);
        TreeNode eight=new TreeNode(8);

        TreeNode nine=new TreeNode(9);
        TreeNode ten=new TreeNode(10);


        one.left=two; one.right=three;

        two.left=four;two.right=five;

        three.left=six;three.right=seven;


        five.left=eight;

        six.right=nine;

        seven.right=ten;


        PRintBinaryTreeBoundary p=new PRintBinaryTreeBoundary();
        p.print(one);





    }

    private void print(TreeNode one) {
        System.out.println(one.val);

        populateLeftBorderList(one.left);
        populateRightBorderList(one.right);

        populateLeafOfLeftTree(one.left);
        populateLeafOfRightTree(one.right);


        System.out.println(this.leftBorderList);
        System.out.println(this.leftLEafNode);

        System.out.println(this.rightLEafNode);
        Collections.reverse(this.rightBorderList);
        System.out.println(this.rightBorderList);



    }

    private void populateLeftBorderList(TreeNode node) {

        TreeNode n = node;

        while (n != null) {
            this.leftBorderList.add(n);
            n = n.left;
        }

    }

    private void populateRightBorderList(TreeNode node) {

        TreeNode n = node;
        while (n != null) {
            this.rightBorderList.add(n);
            n = n.right;
        }

    }

    private void populateLeafOfLeftTree(TreeNode leftnode) {

        Queue<TreeNode> q = new LinkedList<>();
        q.add(leftnode);

        while (!q.isEmpty()) {

            TreeNode n = q.remove();

            if (null == n.left && null == n.right && !this.leftBorderList.contains(n)) {
                leftLEafNode.add(n);
            }

            if (null != n.left)
                q.add(n.left);

            if (null != n.right)
                q.add(n.right);

        }
    }

    private void populateLeafOfRightTree(TreeNode rightNode) {

        Queue<TreeNode> q = new LinkedList<>();
        q.add(rightNode);

        while (!q.isEmpty()) {

            TreeNode n = q.remove();

            if (null == n.left && null == n.right && !this.rightBorderList.contains(n)) {
                rightLEafNode.add(n);
            }

            if (null != n.left)
                q.add(n.left);

            if (null != n.right)
                q.add(n.right);

        }

    }
}

- Nirav Shah

Answer 5

希望这可以帮到你：

// Java program to print boundary traversal of binary tree 

/* A binary tree node has data, pointer to left child 
   and a pointer to right child */
class Node { 
int data; 
Node left, right; 

 Node(int item) 
 { 
    data = item; 
    left = right = null; 
 } 
} 

class BinaryTree { 
Node root; 

// A simple function to print leaf nodes of a binary tree 
void printLeaves(Node node) 
{ 
    if (node != null) { 
        printLeaves(node.left); 

        // Print it if it is a leaf node 
        if (node.left == null && node.right == null) 
            System.out.print(node.data + " "); 
        printLeaves(node.right); 
    } 
} 

// A function to print all left boundary nodes, except a leaf node. 
// Print the nodes in TOP DOWN manner 
void printBoundaryLeft(Node node) 
{ 
    if (node != null) { 
        if (node.left != null) { 

            // to ensure top down order, print the node 
            // before calling itself for left subtree 
            System.out.print(node.data + " "); 
            printBoundaryLeft(node.left); 
        } 
        else if (node.right != null) { 
            System.out.print(node.data + " "); 
            printBoundaryLeft(node.right); 
        } 

        // do nothing if it is a leaf node, this way we avoid 
        // duplicates in output 
    } 
} 

// A function to print all right boundary nodes, except a leaf node 
// Print the nodes in BOTTOM UP manner 
void printBoundaryRight(Node node) 
{ 
    if (node != null) { 
        if (node.right != null) { 
            // to ensure bottom up order, first call for right 
            // subtree, then print this node 
            printBoundaryRight(node.right); 
            System.out.print(node.data + " "); 
        } 
        else if (node.left != null) { 
            printBoundaryRight(node.left); 
            System.out.print(node.data + " "); 
        } 
        // do nothing if it is a leaf node, this way we avoid 
        // duplicates in output 
    } 
} 

// A function to do boundary traversal of a given binary tree 
void printBoundary(Node node) 
{ 
    if (node != null) { 
        System.out.print(node.data + " "); 

        // Print the left boundary in top-down manner. 
        printBoundaryLeft(node.left); 

        // Print all leaf nodes 
        printLeaves(node.left); 
        printLeaves(node.right); 

        // Print the right boundary in bottom-up manner 
        printBoundaryRight(node.right); 
    } 
} 

// Driver program to test above functions 
public static void main(String args[]) 
{ 
    BinaryTree tree = new BinaryTree(); 
    tree.root = new Node(20); 
    tree.root.left = new Node(8); 
    tree.root.left.left = new Node(4); 
    tree.root.left.right = new Node(12); 
    tree.root.left.right.left = new Node(10); 
    tree.root.left.right.right = new Node(14); 
    tree.root.right = new Node(22); 
    tree.root.right.right = new Node(25); 
    tree.printBoundary(tree.root); 
} 
} 

二叉树的边界遍历

- Yash P Shah

Answer 6

以下是一个Java O(n)时间复杂度的解决方案，用于解决计算重复项（例如：同时是左节点和叶子节点）的问题。

class Node {
    Node left;
    Node right;
    int data;
    Node(int d) {
       data = d;
       left = right = null;
    }
}

class BinaryTree {
    Node root;
    public void getBoundary() {
       preorderLeft(root);
       inorderLeaves(root);
       postorderRight(root);
    }
    public boolean isLeaf(Node node) {
       if (node != null && node.left == null && node.right == null) return true;
       return false;
    }
    public void preorderLeft(Node start) {
       if (start != null && isLeaf(start) == false) System.out.print(start.data + " ");
       if (start.left != null) preorderLeftSide(start.left);
    }
    public void inorderLeaves(Node start) {
       if(start == null) return;
       if(start.left != null) inorderLeaves(start.left);
       if(start.left == null && start.right == null) System.out.print(start.data + " ");
       if(start.right != null) inorderLeaves(start.right);
    }
    public void postorderRight(Node start) {
       if(start.right != null) postorderRightSide(start.right);
       if(start != null && isLeaf(start) == false) System.out.print(start.data + " ");
    }
}

这个YouTube视频非常有帮助。作者写了注释来解释每种方法，并展示了如何跳过重复项。https://youtu.be/7GzuxmZ34cI

- kundus

Answer 7

通过使用根节点的垂直距离和层级，我们可以使用列表和映射来解决它。

map<int,int>tmap;    #store the vertical distance and level
list<int>llist;  #store the node values

void Buildfunction(root,d, l){
    if(root == NULL){
        return; 
    } else if(tmap.count(d) == 0){
       tmap[d] = l;
       llist.push_back(root->data);
    } else if((root->left == NULL && root->right==NULL) || tmap[d] < l){
       tmap[d] = l;
       llist.push_back(root->data);  
    }
    Buildfunction(root->left,d--,l++);
    Buildfunction(root->right,d++,l++);  
}

d指向当前节点相对于根节点的垂直距离，l指向从0开始的当前节点的级别

- Dinkar Jaiswar

Answer 8

以下的Python解决方案对我有效。它处理了所有情况。 基于@azt的解决方案

class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def printLeaves(root):
    if (root):
        printLeaves(root.left)
        if root.left is None and root.right is None:
            print(root.data),

        printLeaves(root.right)


def printBoundaryC(node):
    if not node.left or not node.right:
        print(node.data)
    if node.left:
        printBoundaryC(node.left)
    if node.right:
        printBoundaryC(node.right)


def printBoundaryLeft(root):
    print(root.data)
    if root.left:
        printBoundaryLeft(root.left)
    if root.right:
        printBoundaryC(root.right)

def printBoundaryRight(root):
    if root.right:
        printBoundaryRight(root.right)
    elif root.left:
        printBoundaryC(root.left)
    print(root.data)

def printBoundary(root):
    if (root):
        print(root.data)

        if root.left:
            printBoundaryLeft(root.left)
        if root.right:
            printBoundaryRight(root.right)



root = Node(20)
root.left = Node(8)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.left.right = Node(5)
root.left.right.right = Node(14)
root.right = Node(22)
root.right.right = Node(25)
printBoundary(root)

- rok