打印二叉树每一层除了最右节点的所有节点

---

在这个问题中，我们将打印二叉树中除了每一层最右节点之外的所有节点。

我们将使用层序遍历来遍历二叉树，并且我们不会打印每一层的最后一个节点，也就是最右节点。

问题陈述 − 我们给定一个包含不同节点的二叉树。我们需要打印二叉树中除了最右节点之外的所有节点。

示例

输入 

          7
       /     \
      8       9
    /   \       \
   2     7       21
        /  \
       21    43

输出

8
2  7
21

解释：我们打印了每一层除了最右节点之外的所有节点。

输入

             35
           /    \    
         74     21    
        /  \    / \       
      32    15 90  576        
     /  \
    45  83

输出 

74
32 15 90
45

解释 −在这里，我们打印除了最右节点之外的所有节点。

方法一

在这种方法中，我们将使用队列对给定的二叉树执行层序遍历。在层序遍历中，我们不会打印每一层的最后一个节点，以排除每一层的最右节点。

算法

步骤 1− 为二叉树节点创建一个 TreeNode 结构。树节点包含用于存储数据的 ‘val’ 以及用于跟踪特定节点的左孩子和右孩子节点的 ‘left’ 和 ‘right’ 指针。

步骤 2 − 之后，定义 createNode() 函数来创建一个新节点。

步骤 2.1 − 创建一个新的 ‘tmp’ 节点，并使用给定的值初始化其值。同时，将左指针和右指针初始化为 NULL。

步骤 2.2 − 从函数返回 ‘tmp’ 节点。

步骤 3 − 在 main() 方法中，通过添加节点来创建一个二叉树。

步骤 4 − 执行 printNodes() 函数以打印二叉树的每个节点，除了二叉树的最右节点。

步骤 5 − 在 printNodes() 函数中，如果头指针为 NULL，则执行 return 语句。

步骤 6 − 定义队列来存储树节点并插入头节点。

步骤 7 − 使用 while 循环进行迭代。在 while 循环中，将队列大小存储在 ‘totalNodes’ 变量中。

步骤 8 − 如果 ‘totalNodes’ 为 0，则中断循环。

步骤 9 − 使用嵌套 while 循环遍历每一层。

步骤 10 − 从队列中弹出第一个元素，如果 ‘totalNodes’ 不等于 1，则打印它。

步骤 11 − 如果当前节点的左孩子存在，则将其推入队列。

步骤 12 − 如果当前节点的右节点存在，则将其推入队列。

步骤 13 − 将 ‘totalNodes’ 减 1。

示例

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};
TreeNode *createNewNode(int val) {
    TreeNode *tmp = new TreeNode;
    tmp->val = val;
    tmp->left = NULL;
    tmp->right = NULL;
    return (tmp);
}
void printNodes(TreeNode *head) {
    if (head == NULL)
        return;
    queue<TreeNode *> que;
    que.push(head);
    while (true) {
        int totalNodes = que.size();
        if (totalNodes == 0)
            break;
        while (totalNodes > 0) {
            TreeNode *node = que.front();
            // If node is not rightmost print
            if (totalNodes != 1)
                cout << node->val << " ";
            que.pop();
            // Insert the left and right node of the current node in the queue
            if (node->left != NULL)
                que.push(node->left);
            if (node->right != NULL)
                que.push(node->right);
            totalNodes--;
        }
        cout << "\n";
    }
}
int main() {
    TreeNode *head = createNewNode(35);
    head->left = createNewNode(74);
    head->right = createNewNode(21); 
    head->right->left = createNewNode(90);
    head->right->right = createNewNode(576);
    head->left->left = createNewNode(32);
    head->left->right = createNewNode(15);
    head->left->left->left = createNewNode(45);
    head->left->right->right = createNewNode(83);
    printNodes(head);
    return 0;
}

输出

74 
32 15 90 
45

时间复杂度 − O(N)，其中 N 是二叉树中节点的总数。

空间复杂度 − O(M)，其中 M 是一个层级中节点的最大数量。

我们学习了如何使用层序遍历来打印除了最右节点之外的每个二叉树节点。但是，程序员可以编写代码来打印除了最左节点之外的每个二叉树节点。在这种情况下，程序员需要打印队列中除了第一个节点之外的所有节点。