打印二叉树的边界

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 traversal (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) 阶的额外内存。

我的问题是，告诉我一个遍历树单次的方法，不使用任何布尔变量，不使用任何额外的内存。可能吗？

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 函数开始。摆脱了每个方法开头的空查询（避免在每一端调用一个函数）。不需要bool变量，简单的使用三种不同的遍历方式：

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

Answer 2

下面是Python3中的递归解法，时间复杂度为O(n)。这里的算法是从上到下打印最左边的节点，从左到右打印叶节点，从下到上打印最右边的节点。为左右树遍历添加布尔标志 (isLeft,isRight) 简化了代码并推动了 O(n) 的时间复杂度。

#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)

Answer 3

方法O(n) No extra space and single traversal of tree.

我把Tree Nodes分为四种类型的节点

Type 1 -> Nodes which form the left boundary(eg 8)

Type 0 -> Nodes which do not form the boundar(eg 12)

Type 3 -> Nodes which form the right boundary(eg 22)

Leaf Nodes(eg 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，必须在调用它们的 children 之前打印（如果它们存在)
类型 3 的节点 必须以相反的顺序打印。因此它们必须是在调用他们的 children.They 后打印还必须分配他们的右 children 作为类型 3 节点
类型 0 的节点不得打印，它们将 children 指定为类型 0 节点
叶节点必须直接打印，return

Link to Code

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

        }

    }
}

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

Boundary Traversal of binary tree

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

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

开始的level

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)

打印二叉树的边界

To print the boundary of Binary Tree

algorithm

tree

binary-tree

graph-algorithm

binary-search-tree