C++ 二叉树的边界层次遍历

在这个问题中，我们会按照给定顺序遍历给定二叉树的每个边界。

我们将使用递归的方法逐个遍历二叉树的每个边界。然而，我们还将学习使用栈的迭代方法来遍历二叉树的边界并提高代码的性能。

问题描述

我们给定一个二叉树，我们需要按照给定顺序遍历树的每个边界。

从上到下遍历左边界。
从左到右遍历底部边界。
从下到上遍历右边界。

示例

输入

4
 /   \
8     9

输出

4, 8, 9

解释

我们遍历树的边界。

输入

输出

9, 6, 10, 12, 3, 8,

解释

我们可以将9、6、10和12视为左边界。我们可以将10、12和3视为底边界。我们可以将3、8和9视为右边界。在这里，我们打印了所有边界元素一次。

方法1

在这个方法中，我们将编写3个递归函数来遍历左边界、底边界和右边界的每个节点。

算法

步骤1 - 创建一个包含整数变量、左右指针和构造函数以初始化节点的treenode类。
步骤2 - 在main()方法中创建一个二叉树，并执行traverseBoundary()函数。
步骤3 - 在traverseBoundary()函数中，如果头节点为null，则执行返回语句。否则，打印头节点的值。
步骤4 - 对左子树调用showLeft()函数以遍历左边界。
步骤4.1 - 在showLeft()函数中，如果头节点为null或不包含子节点，则从函数中返回。
步骤4.2 - 如果左子节点存在，则打印它的值，并将其作为参数传递给showLeft()函数。否则，打印右子节点的值，并对右子节点执行showLeft()函数。
步骤5 - 执行showBottom()函数以显示左子树和右子树的边界。
步骤5.1 - 在showBottom()函数中，如果头节点为null，则执行返回语句。
步骤5.2 - 如果当前节点是叶节点，则打印它的值。
步骤5.3 - 对左子节点和右子节点执行showBottom()函数。
步骤6 - 执行showRight()函数以遍历右边界。
步骤6.1 - 在showRight()函数中，如果头节点为null或不包含子节点，则执行返回语句。
步骤6.2 - 如果右节点不为null，则对右子树执行showRight()函数，并打印右节点的值。这里，我们在函数调用后打印节点的值，因为我们需要从底部向上遍历树。
步骤6.3 - 如果右子节点不存在但左子节点存在，则对左子节点进行递归调用，并在调用后打印它的值。

示例

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

class treenode {
   public:
      int val;
      treenode *left, *right;
   // constructor
   treenode() {
      left = NULL;
      right = NULL;
   }
};
void showBottom(treenode *head) {
   // Base case
   if (head == NULL)
      return;
   // When head node is a leaf node
   if ((head->left) == NULL && (head->right) == NULL)
      cout << head->val << " ";
   // Traverse left subtree
   showBottom(head->left);
   // Traverse the right subtree
   showBottom(head->right);
}
void showLeft(treenode *head) {
   if (head == NULL && (head->left == NULL && head->right == NULL))
      return;
   // When the left child exists
   if (head->left != NULL) {
      cout << head->val << " ";
      // Recursive function call
      showLeft(head->left);
   } else if (head->right != NULL) {
      // When the left child not exists
      cout << head->val << " ";
      showLeft(head->right);
   }
}
void showRight(treenode *head) {
   // Base case
   if (head == NULL || (head->left == NULL && head->right == NULL))
      return;
   // When a right child is present
   if (head->right != NULL) {
      showRight(head->right);
      cout << head->val << " ";
   }
   // When the right child is not present
   else if (head->left != NULL) {
      showRight(head->left);
      cout << head->val << " ";
   }
}
void traverseBoundary(treenode *head) {
   // When the tree is null
   if (head == NULL)
      return;
   // pRoot node
   cout << head->val << " ";
   // Showing left boundary
   showLeft(head->left);
   // Showing the bottom of the left subtree
   showBottom(head->left);
   // Showing the bottom of the right subtree
   showBottom(head->right);
   // Show the right boundary
   showRight(head->right);
}
treenode *createNewNode(int val) {
   treenode *temp = new treenode();
   temp->val = val;
   return temp;
}
int main() {
   treenode *head = createNewNode(9);
   head->left = createNewNode(6);
   head->right = createNewNode(8);
   head->left->left = createNewNode(10);
   head->left->right = createNewNode(53);
   head->left->right->left = createNewNode(12);
   head->left->right->right = createNewNode(3);
   traverseBoundary(head);
}

输出

9 6 10 12 3 8

时间复杂度 - O(N) 对每个节点进行遍历。
空间复杂度 - O(H) 用于递归栈。

方法2

在这种方法中，我们将使用堆栈数据结构来遍历二叉树的每个边界。

算法

步骤1 - 如果头节点不为空，执行以下步骤。
步骤2 - 如果头节点没有子节点，则打印其值并返回。
步骤3 - 定义l_nodes列表。遍历树的每个左节点并将其推入l_nodes。
步骤4 - 定义stack_1和stack_2分别存储所有节点和叶子节点。将头节点插入stack1。
步骤5 - 现在，循环直到stack1变为空。
步骤5.1 - 在循环中，从堆栈中弹出节点。如果它们存在子节点，则将子节点插入堆栈。如果子节点不存在，则将节点插入stack_2。
步骤6 - 现在，将stack_2的所有元素插入l_nodes。
步骤7 - 现在，定义rightNode列表，遍历所有右节点，并将它们插入列表中。还要将rightNodes列表反转。
步骤8 - 将rightNodes的所有节点附加到l_nodes列表中，并打印l_nodes的元素。

示例

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

class treenode {
   public:
      int val;
      treenode *left, *right;
   // constructor
   treenode() {
      left = NULL;
      right = NULL;
   }
};
void traverseBoundary(treenode *head) {
   if (head != NULL) {
      // For a tree with a single node
      if ((head->left == NULL) && (head->right == NULL)) {
         cout << head->val << endl;
         return;
      }        
      vector<treenode *> l_nodes; // To store node order
      l_nodes.push_back(head);        
      treenode *leftNode = head->left; // For left boundary traversal
      // Insert left noes in the list
      while (leftNode->left) {
         l_nodes.push_back(leftNode);
         leftNode = leftNode->left;
      }        
      stack<treenode *> stack_1; // To store all nodes        
      stack<treenode *> stack_2; // For storing leaf nodes      
      stack_1.push(head); // Insert head
      while (!stack_1.empty()) {
         treenode *temp = stack_1.top();
         stack_1.pop();
         // Insert left child in a stack
         if (temp->left)
            stack_1.push(temp->left);
            // Insert right child in the stack
            if (temp->right)
               stack_1.push(temp->right);
            // For leaf node
            else if (!temp->left && !temp->right)
               stack_2.push(temp);
      }
      // Show all leaf nodes
      while (!stack_2.empty()) {
         l_nodes.push_back(stack_2.top());
         stack_2.pop();
      }        
      vector<treenode *> rightNodes; // Right boundary
      treenode *r_node = head->right;
      while (r_node->right) {
         rightNodes.push_back(r_node);
         r_node = r_node->right;
      }        
      reverse(rightNodes.begin(), rightNodes.end()); // Revere right node order    
      l_nodes.insert(l_nodes.end(), rightNodes.begin(), rightNodes.end()); // Merge two list
      // Printing the boundary traversal
      for (auto p : l_nodes) {
         cout << p->val << " ";
      }
      cout << endl;
      return;
   }
}
treenode *createNewNode(int val) {
   treenode *temp = new treenode();
   temp->val = val;
   return temp;
}
int main() {
   treenode *head = createNewNode(9);
   head->left = createNewNode(6);
   head->right = createNewNode(8);
   head->left->left = createNewNode(10);
   head->left->right = createNewNode(53);
   head->left->right->left = createNewNode(12);
   head->left->right->right = createNewNode(3);
   traverseBoundary(head);
}