二叉樹的邊界遍歷  


難度級別 中烘焙
經常問 ol石 亞馬遜 遠足 Kritikal解決方案 Microsoft微軟 摩根士丹利(Morgan Stanley) 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是樹的高度。 這是因為編譯器堆棧使用空間。 用於打印邊界元素的函數使用遞歸,該遞歸對於編譯器堆棧很重要。