数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究二叉树的边界级别遍历
在这个问题中，我们将按照给定的顺序遍历给定二叉树的每个边界。
我们将使用递归方法依次遍历二叉树的每个边界。但是，我们还将学习使用栈的迭代方法来遍历二叉树的边界，并提高代码的性能。
问题陈述
我们得到了一棵二叉树，我们需要按照给定的顺序遍历树的每个边界。
从上到下遍历左边界。
从左到右遍历底边界。
从下到上遍历右边界。
示例
输入
4 / \ 8 9
输出
4, 8, 9
解释
我们遍历树的边界。
输入
9
/ \
6 8
/ \
10 53
/ \
12 3
输出
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() 函数中，如果 head 为空，则执行 return 语句。否则，打印 head 节点的值。
步骤 4 - 调用 showLeft() 函数以获取左子树，从而遍历左边界。
步骤 4.1 - 在 showLeft() 函数中，如果 head 为空或不包含子节点，则从函数返回。
步骤 4.2 - 如果存在左子节点，则打印其值，并通过将其作为参数传递来调用 showLeft() 函数。否则，打印右子节点的值，并对右子节点执行 showLeft() 函数。
步骤 5 - 执行 showBottom() 函数以显示左子树和右子树的边界。
步骤 5.1 - 在 showBottom() 函数中，如果 head 为空，则执行 return 语句。
步骤 5.2 - 如果当前节点是叶子节点，则打印其值。
步骤 5.3 - 对左子节点和右子节点执行 showBottom() 函数。
步骤 6 - 执行 showRight() 函数以遍历右边界。
步骤 6.1 - 在 showRIght() 函数中，如果 head 为空或不包含子节点，则执行 return。
步骤 6.2 - 如果右节点不为空，则对右子树执行 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 - 当 head 不为空时，执行以下步骤。
步骤 2 - 如果 head 不包含任何子节点，则打印其值并从函数返回。
步骤 3 - 定义 l_nodes 列表。遍历树的每个左节点并将其推入 l_nodes。
步骤 4 - 定义 stack_1 和 stack_2 分别存储所有节点和叶子节点。将 head 节点插入 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);
}
输出
9 6 10 12 3 8
时间复杂度 - O(N)
空间复杂度 - O(N)
使用栈的迭代方法比递归方法更快，但消耗更多内存，这可能不适合处理大型数据。
126 次浏览
