二叉树的边界遍历  


难度级别 中等
经常问 ol石 亚马逊 远足 Kritikal解决方案 微软 摩根士丹利 PayU Snapdeal
二叉树 树遍历

问题陈述  

问题“二叉树的边界遍历”指出给您一棵二叉树。 现在,您需要打印 二叉树。 这里的边界遍历意味着所有节点都显示为树的边界。 从逆时针方向的顶部,左侧,底部和右侧可以看到节点。 但是,如果我们直接打印所有这些视图,将导致多次打印相同的节点。 因此,请打印边界视图,以使节点不会重复。

使用案列  

2 3 5 6 4 7

说明

在这里,所有节点都是边界节点。 但是我们需要沿逆时针方向打印节点。 因此,我们从2的根开始。然后,我们以相同的方式简单地移动并打印节点2、3、4、6、4、7。

二叉树的边界遍历

5 7 9 1 4 3

途径  

这个问题要求我们打印树的边界,这里我们有左边界,右边界和下边界。 如果树没有任何左边界或右边界。 根本身被视为左边界或右边界。 还有一个条件是,如果我们打印边界节点,则需要注意两个节点都不打印多次。

为了解决这个问题,我们将从树的左边界开始。 我们说一个节点属于左侧边界,如果该节点从左侧可见。 同样,我们定义右侧节点和叶节点。 为了打印左边界,我们将以这样的方式遍历树,即如果根具有左节点,则移至该树,否则移至其右节点。 一旦到达叶节点。 我们不打印叶节点,因为我们递归地分别打印叶节点。 一旦我们完成了左边界。

参见
在二叉树中找到最大级别总和

通过首先打印左子树叶子,我们打印叶子节点。 打印左子树叶子后,在右子树中打印叶子。 这样,所有叶子节点将以逆时针方向打印。 打印叶子后,我们将打印右边界的节点。 这次需要以自下而上的方式打印节点。 因此在 递归,首先我们求解树的左或右子树,然后对当前节点进行pMicrrint。

C ++代码打印二叉树的边界遍历  

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

// print the leaves (nodes from the bottom)
void printLeaves(node* root)
{
  if(root){
    // recursively solve the problem for the left subtree
    printLeaves(root->left);
    // if current node is a leaf
    if ((root->left) == NULL && (root->right) == NULL)
      cout<<root->data<<" ";
    // recursively solve the problem for right subtree
    printLeaves(root->right);
  }
}

// print all the nodes of left boundary
// this function will not print the leaves viewed from left side
void printLeft(node* root)
{
  if(root){
    if(root->left != NULL){
      cout<<root->data<<" ";
      // recursively move down the left subtree
      printLeft(root->left);
    }
    else if(root->right){
      cout<<root->data<<" ";
      // recursively move down the right subtree
      printLeft(root->right);
    }
  }
}

// print all the nodes of right boundary
// this function will not print the leaves viewed from the right side
void printRight(node* root)
{
  // printing is done after moving down the tree
  // thus printing is done in bottom up manner
  if(root){
    if (root->right) {
      printRight(root->right);
      cout<<root->data<<" ";
    }
    else if (root->left) {
      printRight(root->left);
      cout<<root->data<<" ";
    }
  }
}

void boundaryUtil(node* root)
{
  // first print the root, then print the left boundary
  // then the leaves which are seen from bottom
  // at last print the right boundary
  if(root){
    cout<<root->data<<" ";
    printLeft(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRight(root->right);
  }
}

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);

  boundaryUtil(root);
}
5 7 9 1 4 3

Java代码打印二叉树的边界遍历  

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  // print the leaves (nodes from the bottom)
  static void printLeaves(node root)
  {
    if(root != null){
      // recursively solve the problem for the left subtree
      printLeaves(root.left);
      // if current node is a leaf
      if ((root.left) == null && (root.right) == null)
        System.out.print(root.data+" ");
      // recursively solve the problem for right subtree
      printLeaves(root.right);
    }
  }

  // print all the nodes of left boundary
  // this function will not print the leaves viewed from left side
  static void printLeft(node root)
  {
    if(root != null){
      if(root.left != null){
        System.out.print(root.data+" ");
        // recursively move down the left subtree
        printLeft(root.left);
      }
      else if(root.right != null){
        System.out.print(root.data+" ");
        // recursively move down the right subtree
        printLeft(root.right);
      }
    }
  }

  // print all the nodes of right boundary
  // this function will not print the leaves viewed from the right side
  static void printRight(node root)
  {
    // printing is done after moving down the tree
    // thus printing is done in bottom up manner
    if(root != null){
      if(root.right != null){
        printRight(root.right);
        System.out.print(root.data+" ");
      }
      else if(root.left != null){
        printRight(root.left);
        System.out.print(root.data+" ");
      }
    }
  }

  static void boundaryUtil(node root)
  {
    // first print the root, then print the left boundary
    // then the leaves which are seen from bottom
    // at last print the right boundary
    if(root != null){
      System.out.print(root.data+" ");
      printLeft(root.left);
      printLeaves(root.left);
      printLeaves(root.right);
      printRight(root.right);
    }
  }

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  public static void main(String[] args){
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    boundaryUtil(root);
  }
}
5 7 9 1 4 3

复杂度分析  

时间复杂度

上), 因为我们已经遍历了树的所有节点。 当我们使用printLeft,printRight和printLeaves函数时,我们将遍历节点。 因此,时间复杂度是线性的。

参见
从链接列表表示构造完整的二叉树

空间复杂度

哦), 其中H是树的高度。 这是因为编译器堆栈使用空间。 用于打印边界元素的函数使用递归,该递归对于编译器堆栈很重要。